这道题就是Dijkstra，没有用到DFS神马的~
个人觉得Dijkstra就是细节太多，很容易写错或者忘记一些什么的。。。提交了好几次。。。然后参考了大佬的代码~
#include<cstdio> #include<string.h> #include<algorithm> using namespace std; const int maxn = 500; const int INF = 1000000000; int G[maxn][maxn], weight[maxn]; int num[maxn], w[maxn]; int n, m, st, ed, d[maxn]; bool vis[maxn] = { false }; void Dijkstra(int s) { fill(d, d + maxn, INF); memset(num, 0, sizeof(num)); memset(w, 0, sizeof(w)); w[s] = weight[s]; //这里的初始化别忘记写啊！！！！不然肯定是答案错误啊！！！ d[s] = 0; num[s] = 1; //这里num[s]初始化为1啊！！！！ for (int i = 0; i < n; i++) { //循环n次 注意这里的括弧啊！！！！！包含两个for！！！！ int u = -1, MIN = INF; for (int j = 0; j < n; j++) { if (vis[j] == false && d[j] < MIN) { //遍历从点i出发的，能从st到达的，还未被揭露边权的点 u = j; //d[0]==0,u=0,MIN=0; 选出离st最近的下一个顶点； MIN = d[j]; } } if (u == -1) return; vis[u] = true; for (int v = 0; v < n; v++) { //v==1;d[1]=G[0][1]+0;...d[3]=...; if (vis[v] == false && G[u][v] != INF) { if (d[v] > G[u][v] + d[u]) { d[v] = G[u][v] + d[u]; w[v] = w[u] + weight[v]; num[v] = num[u]; } else if (d[v] == G[u][v] + d[u]) { if (w[v] < w[u] + weight[v]) { //第二条件一定要写清楚啊~不能没if就直接赋值 w[v] = w[u] + weight[v]; } num[v] += num[u]; } } } } } int main() { scanf("%d%d%d%d", &n, &m, &st, &ed); for (int i = 0; i < n; i++) { scanf("%d", &weight[i]); } fill(G[0], G[0] + maxn*maxn, INF); //敲重点！！注意二维数组的fill()形式 for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); scanf("%d", &G[a][b]); G[b][a] = G[a][b]; //敲重点！！不能忘记写啊~ } Dijkstra(st); printf("%d %d\n", num[ed], w[ed]); return 0; }
