HDU Today
http://acm.hdu.edu.cn/showproblem.php?pid=2112
?
| Problem Description 經過錦囊相助，海東集團終于度過了危機，從此，HDU的發展就一直順風順水，到了2050年，集團已經相當規模了，據說進入了錢江肉絲經濟開發區500強。這時候，XHD夫婦也退居了二線，并在風景秀美的諸暨市浬浦鎮陶姚村買了個房子，開始安度晚年了。 ? ?Input 輸入數據有多組，每組的第一行是公交車的總數N(0<=N<=10000)； ? ?Output 如果徐總能到達目的地，輸出最短的時間；否則，輸出“-1”。 ? ?Sample Input 6 xiasha westlake xiasha station 60 xiasha ShoppingCenterofHangZhou 30 station westlake 20 ShoppingCenterofHangZhou supermarket 10 xiasha supermarket 50 supermarket westlake 10 -1 ? ?Sample Output 50 Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake 雖然偶爾會迷路，但是因為有了你的幫助 **和**從此還是過上了幸福的生活。 ――全劇終―― ? ?Author lgx ? ?Source ACM程序設計_期末考試（時間已定！！） ? ?Recommend lcy???|???We have carefully selected several similar problems for you:??2544?1874?1217?2680?1142? |
?
C++版本一
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUGusing namespace std; typedef long long ll; const int N=50; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int n; int edgenum; int head[20005]; char ex[35],ey[35]; int vis[155]; int dis[155];struct Edge {int from,to,val,next; }edge[20005]; void addedge(int u,int v,int w) {Edge E={u,v,w,head[u]};edge[edgenum]=E;head[u]=edgenum++; } map<string,int>mp; int t;int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(scanf("%d",&n)&&(n!=-1)){edgenum=0;memset(head,-1,sizeof(head));mp.clear();//一定要清零！getchar();scanf("%s%s",ex,ey);mp[ex]=1;t=2;if(!mp[ey]){mp[ey]=t++;}char a[35],b[35];int c;for(int i=1;i<=n;i++){getchar();scanf("%s%s%d",a,b,&c);if(!mp[a]){mp[a]=t++;}if(!mp[b]){mp[b]=t++;}addedge(mp[a],mp[b],c);addedge(mp[b],mp[a],c);}queue<int>q;q.push(1);memset(vis,0,sizeof(vis));memset(dis,INF,sizeof(dis));vis[1]=1;dis[1]=0;while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(dis[v]>dis[u]+edge[i].val){dis[v]=dis[u]+edge[i].val;if(vis[v]==0){vis[v]=1;q.push(v);}}}}if(dis[mp[ey]]==INF)printf("-1\n");elseprintf("%d\n",dis[mp[ey]]);}return 0; }C++版本二
剛開始沒有考慮起終點不在路徑內的情況
/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUGusing namespace std; typedef long long ll; const int N=50; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int n,m; char s[N],t[N]; struct node {int e,w; }; struct cmp{bool operator()(const node &a,const node &b){return a.w>b.w;} }; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(~scanf("%d",&n)&&n!=-1){scanf("%s%s",s,t);priority_queue<node,vector<node>,cmp>que;vector<node>v[200];int vis[200]={0};node x;map<string ,int >ma;char a[N],b[N];int c,cnt=0;if(!ma[s]){ma[s]=++cnt;}if(!ma[t]){ma[t]=++cnt;}for(int i=1;i<=n;i++){scanf("%s%s%d",a,b,&c);if(!ma[a]){ma[a]=++cnt;}if(!ma[b]){ma[b]=++cnt;}x.e=ma[b];x.w=c;v[ma[a]].push_back(x);x.e=ma[a];v[ma[b]].push_back(x);}x.e=ma[s];x.w=0;que.push(x);while(!que.empty()){x=que.top();que.pop();vis[x.e]=1;if(x.e==ma[t])break;for(int i=0,j=v[x.e].size();i<j;i++){node q;q.e=v[x.e][i].e;if(vis[q.e])continue;q.w=x.w+v[x.e][i].w;que.push(q);}}if(x.e==ma[t])cout << x.w << endl;elsecout << -1 << endl;}//cout << "Hello world!" << endl;return 0; }?
總結
