hdu 2112

最开始顶点个数不明确顶点从1开始编号，循环也从1开始记得要清空map（会导致mle）注意重边map查询对应的关系需要logn的时间，所以当调用多次一样的变量的时候需要记录下来，可以节约时间每次找出离起点最近的点记得标记vis[p]=1; #include <cstdio> #include <cstring> #include <map> #include <string> #include <vector> #include <iostream> using namespace std; const int INF=0x3f3f3f3f,N=155; int w[N][N],vis[N],dis[N]; char a[37],b[37]; map<string,int> q; int main() { int n; while(scanf("%d",&n)) { if(n==-1) break; q.clear(); for(int i=1;i<=150;i++)//因为不确定地点的个数所以全部初始化 for(int j=1;j<=150;j++) if(i==j) w[i][j]=0; else w[i][j]=INF; scanf("%s%s",a,b); int cnt=0; q[a]=++cnt,q[b]=++cnt;//地点个数 int s=q[a],d=q[b]; for(int i=1;i<=n;i++) { int c; scanf("%s%s%d",a,b,&c); if(!q.count(a)) q[a]=++cnt; if(!q.count(b)) q[b]=++cnt; int id1=q[a],id2=q[b]; if(c<w[id1][id2]) w[id1][id2]=w[id2][id1]=c; } for(int i=1;i<=cnt;i++) dis[i]=w[s][i],vis[i]=0; vis[s]=1; dis[s]=0; while(1) { int p=-1,mi=INF; for(int i=1;i<=cnt;i++) if(dis[i]<mi&&!vis[i]) mi=dis[p=i]; if(p==-1) break; vis[p]=1; for(int i=1;i<=cnt;i++) if(dis[i]>(w[p][i]+dis[p])&&!vis[i]) dis[i]=w[p][i]+dis[p]; } if(dis[d]!=INF) printf("%d\n",dis[d]); else printf("-1\n"); } }