哭了哭了，这个题目本身很简单，但是我把一个结点默认值设置成了0，导致后三个测试点无法通过，我分析了大半天觉得自己的逻辑很清晰，不会出错。。。结果是因为一个小细节。。。
附本人AC代码：
#include<iostream> #include<vector> #include<set> using namespace std; const int inf = 1000000000; vector<int>pval; bool flag[510]; int map[510][510], dis[510], agval[510], num[510]; int main() { fill(dis,dis + 510, inf); fill(map[0], map[0] + 510 * 510, inf); int N, M, C1, C2, t1, t2, len; scanf("%d%d%d%d", &N, &M, &C1, &C2); pval.resize(N); for (int i = 0; i < N; i++)scanf("%d", &pval[i]); for (int i = 0; i < M; i++) { scanf("%d%d%d", &t1, &t2, &len); map[t1][t2]= len; map[t2][t1] = len; } dis[C1] = 0; agval[C1] = pval[C1]; num[C1] = 1; for (int m = 0;m < N; m++) { int index=-1, mini = inf; for (int i = 0; i < N; i++) { if (dis[i] < mini&&flag[i]==false) { index = i; mini = dis[i]; } } if (index==-1)break; flag[index] = true; for (auto i = 0; i < N; i++) { if (flag[i] == false && map[index][i] != inf) { if (dis[i] > dis[index] + map[index][i]) { dis[i] = dis[index] + map[index][i]; num[i] = num[index]; agval[i] = agval[index] + pval[i]; } else if (dis[i] == dis[index] + map[index][i]) { num[i] += num[index]; if (agval[i] < agval[index] + pval[i])agval[i] = agval[index] + pval[i]; } } } } printf("%d %d", num[C2], agval[C2]); return 0; }