注意点： 看代码注释
#include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <map> #include <cmath> #include <iostream> #include <set> #include <vector> #define INF 0x3f3f3f3f using namespace std; const int N=1e5+5; typedef long long ll; int n,m,s=1,t=2,cnt; map<string,int> q; int bin[205]; int a[205][205]; int dis[205],num[205],kill[205]; int cntn[205],vis[205];//记录最快进攻的条数 int pre[205]; char ss[205][5]; void dij() { for(int i=1; i<=n; i++) vis[i]=0,dis[i]=INF,cntn[i]=num[i]=0,kill[i]=0,pre[i]=-1; dis[s]=0,cntn[s]=1,num[s]=1; //如果起点不标记，那么才能从s->p->i //路径输出才能有Ｓ，而且这样不需要初始化dis,kill，只需将起点那的属性更改 //如果起点标记了，那么s->p这个路径就没有，只有p->i //导致歼敌人数少了bin[p] while(1) { int p=-1; for(int i=1; i<=n; i++) { if(vis[i]) continue; if(p==-1||(dis[i]<dis[p])||(dis[i]==dis[p]&&num[i]>num[p])||(dis[i]==dis[p]&&num[i]==num[p]&&kill[i]>kill[p])) p=i; } if(p==-1)return; vis[p]=1; for(int i=1; i<=n; i++) { if(vis[i])continue; if(dis[i]>dis[p]+a[p][i]) { dis[i]=dis[p]+a[p][i]; num[i]=num[p]+1; kill[i]=kill[p]+bin[i]; cntn[i]=cntn[p]; pre[i]=p; } else if(dis[i]==dis[p]+a[p][i]&&num[i]<num[p]+1) { num[i]=num[p]+1; kill[i]=kill[p]+bin[i]; cntn[i]+=cntn[p];// pre[i]=p; } else if(dis[i]==dis[p]+a[p][i]&&num[i]==num[p]+1&&kill[i]<kill[p]+bin[i]) { kill[i]=kill[p]+bin[i]; cntn[i]+=cntn[p];// pre[i]=p; } else if(dis[i]==dis[p]+a[p][i]) cntn[i]+=cntn[p]; } } } void dfs(int x) { if(x==s) { printf("%s",ss[s]); return; } dfs(pre[x]); printf("->%s",ss[x]); } int main() { char u[5],v[5]; scanf("%d%d%s%s",&n,&m,u,v); q[u]=1,strcpy(ss[1],u),q[v]=2,strcpy(ss[2],v); cnt=2; for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(i==j) a[i][i]=0; else a[i][j]=INF; for(int i=0; i<n-1; i++) { int x; scanf("%s%d",u,&x); if(!q[u]) q[u]=++cnt,strcpy(ss[cnt],u); bin[q[u]]=x; } while(m--) { int w; scanf("%s%s%d",u,v,&w); int uu=q[u],vv=q[v]; if(a[uu][vv]>w) a[uu][vv]=a[vv][uu]=w; } dij(); dfs(t); puts(""); printf("%d %d %d\n",cntn[t],dis[t],kill[t]); }