狄杰斯特拉算法需要注意，最开始的节点往往需要提前处理，不要忘记处理该节点。 最后考虑有几条最短路径的时候，是继承上一节点的值的。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn=1010; const int inf=0x3ffffff; int n,m,w[maxn],G[maxn][maxn],d[maxn],num[maxn]={0},weight[maxn]={0},st,ed; bool vis[maxn]={false}; void dijkstra(int st) { fill(d,d+maxn,inf); d[st]=0; num[st]=1; weight[st]=w[st]; for(int i=0;i<n;i++) { int min=inf,u=-1; for(int j=0;j<n;j++) { if(vis[j]==false&&d[j]<min) { min=d[j]; u=j; } } if(u==-1)return; vis[u]=true; for(int v=0;v<n;v++) { if(vis[v]==false&&G[u][v]!=inf) { if(G[u][v]+d[u]<d[v]) { d[v]=G[u][v]+d[u]; num[v]=num[u]; weight[v]=w[v]+weight[u]; } else if(G[u][v]+d[u]==d[v]) { num[v]+=num[u]; if(weight[v]<w[v]+weight[u]) weight[v]=w[v]+weight[u]; } } } } } int main() { cin>>n>>m>>st>>ed; int c1,c2,l; for(int i=0;i<n;i++) { scanf("%d",&w[i]); } fill(G[0],G[0]+maxn*maxn,inf); for(int i=0;i<m;i++) { scanf("%d %d %d",&c1,&c2,&l); G[c1][c2]=l; G[c2][c1]=l; } dijkstra(st); printf("%d %d",num[ed],weight[ed]); }