题目描述
一个局域网内有很多台电脑，分别标注为 0 ~ N-1 的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用 t 表示。
其中网络内一台电脑被病毒感染，求其感染网络内所有的电脑最少需要多长时间。如果最后有电脑不会感染，则返回-1。
给定一个数组 times 表示一台电脑把相邻电脑感染所用的时间。
如图：path[i] = {i, j, t} 表示：电脑 i->j，电脑 i 上的病毒感染 j，需要时间 t。
输入输出描述
输入
4
3
2 1 1
2 3 1
3 4 1
2输出
2解释
第一个参数：局域网内电脑个数N，1 ≤ N ≤ 200；第二个参数：总共多少条网络连接第三个 2 1 1 表示2->1时间为1第六行：表示病毒最开始所在电脑号2数据预处理
main(){int n;scanf("%d",&n);/*输入顶点的个数*//*初始化邻接矩阵*/int matrix[n+1][n+1];for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){matrix[i][j]=-1;/*全部是离散的点*/}}/*输入边的条数m*/int m;scanf("%d",&m);/*输入邻接矩阵的边权重*/for(int i=0;i<m;i++){int u,v,w;scanf("%d %d %d",&u,&v,&w);matrix[u][v]=w;}/*输入源点src*/int src;scanf("%d",&src);}必要的数据结构
/*是否已经被访问*/bool visited[n+1];/*用来存储src到每个顶点的最短距离*/int dist[n+1];/*初始化*/for(int i=1;i<=n;i++){visited[i]=FALSE;dist[i]=INT_MAX;/*距离初始化为正无穷*/}dist[src]=0;/*二维数组用于记录每个顶点的编号和到源点距离*/int pq[MAX_SIZE][2];int pq_size=0;pq[pq_size][0]=src;pq[pq_size][1]=dist[src];pq_size++;dijkastra解决单源最短路径的主体代码
/*while队不空（数组pq[]实现的顺序队列）*/while(pq_size>0){/*每轮找dist最小的，出队列*/int u=pq[--pq_size][0];if(visited[u]==TRUE) continue;visited[u]=TRUE;/*设置当前选择的结点为已经访问*//*对u的所有邻居*/for(int v=1;v<=n;v++){int w=matrix[u][v];if(w!=-1){int newDist=dist[u]+w;if(newDist<dist[v]){dist[v]=newDist;pq[pq_size][0]=v;/*邻居v入队列pq[]*/pq[pq_size][1]=dist[v];pq_size++;/*按照路径最短进行降序排序*/qsort(pq,pq_size,sizeof(pq[0]),cmp);}}} }输出答案
int sum=0;for(int i=1;i<=n;i++){sum+=dist[i];}printf("%d\n",sum);return 0;}知识补充BFS和Dijkastra
