PAT Emergency dijsktra

本文主要是介绍PAT Emergency dijsktra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先wa了好多次，只有第一个答案是正确的，后来才知道原来是第一个输出是最短路径的个数，一直以为是最短路径。。。。无语了，代码中d[i]代表从c1到节点i的最短路径个数，sum[i]代表最短路径中能集结的最多救援队数，在每次更新节点路径长度的时候要考虑对他们该如何操作。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Max 0x7fffffff - 1000000
long long int gra[505][505];
int num[505];
int d[505];
int n,m,c1,c2,counter;
int visit[505];
int sum[505];int dijsktra()
{int i,j;memset(visit,0,sizeof(visit));visit[c1] = 1;int now = c1;int min;for(i=0; i<n; i++)sum[i] = num[i];sum[c1] = num[c1];for(j=0; j<n; j++){for(i=0; i<n; i++){if(!visit[i]&& gra[c1][i] >= gra[c1][now]+gra[now][i]){if(gra[c1][i] == gra[c1][now]+gra[now][i]){if(now == c1){if(gra[c1][i] == Max)d[i] = 0;elsed[i] = 1;}	elsed[i]+= d[now];if(sum[now]+num[i] > sum[i])sum[i] = sum[now] + num[i];}else{sum[i] = sum[now]+num[i];gra[c1][i] = gra[c1][now]+gra[now][i]; 	d[i] = d[now];}}}min = Max;for(i=0; i<n; i++){if(!visit[i] && gra[c1][i] < min){min = gra[c1][i];now = i;}}visit[now] = 1;if(now == c2)break;}return 0;
}
int main()
{int i,j,a,b,c;scanf("%d%d%d%d",&n,&m,&c1,&c2);for(i=0; i<n; i++)scanf("%d",&num[i]);	for(i=0; i<n; i++)for(j=0; j<n; j++){gra[i][j] = Max;if(i == j)gra[i][j] = 0;} 		for(i=0; i<m; i++){scanf("%d%d%d",&a,&b,&c);gra[a][b] = gra[b][a] = c;}if(c1 == c2){printf("%d %d\n",1,num[c2]);return 0;}	dijsktra();printf("%d %d\n",d[c2],sum[c2]);return 0; 
} 

这篇关于PAT Emergency dijsktra的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---