两遍Dijkstra算法 HDU-3499
Flight
Recently,Shua Shua had a big quarrel with his GF. He is so upset that he decides to take a trip to some other city to avoid meeting her. He will travel only by air and he can go to any city if there exists a flight and it can help him reduce the total cost to the destination. There‘s a problem here: Shua Shua has a special credit card which can reduce half the price of a ticket ( i.e. 100 becomes 50,99 becomes 49. The original and reduced price are both integers. ). But he can only use it once. He has no idea which flight he should choose to use the card to make the total cost least. Can you help him?
InputThere are no more than 10 test cases. Subsequent test cases are separated by a blank line.? 4 4
Harbin Beijing 500
Harbin Shanghai 1000
Beijing Chengdu 600
Shanghai Chengdu 400
Harbin Chengdu
4 0
Harbin Chengdu
Sample Output 800
-1
Hint In the first sample,Shua Shua should use the card on the flight from
Beijing to Chengdu,making the route Harbin->Beijing->Chengdu have the
least total cost 800. In the second sample,there‘s no way for him to get to
Chengdu from Harbin,so -1 is needed.
题意:给出两个城市间的飞机票价格,可以使其中之一价格减半,给出目的地和出发地,求将某一个航班机票价格减半后的最小花费。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<algorithm>
6 #include<map>
7 using namespace std; 8 const int maxn=1000010; 9 const long long inf=99999999999; 10 int head[maxn],vis[maxn]; 11 long long dis1[maxn],dis2[maxn]; 12 int n,m,cnt; 13 struct node{ 14 int pos; 15 long long cost; 16 node(){} 17 node(int pos,long long cost):pos(pos),cost(cost){} 18 friend bool operator < (node a,node b) 19 { 20 return a.cost>b.cost; 21 } 22 }; 23 struct edge{ 24 int to; 25 int next; 26 long long w; 27 }e[maxn]; 28 void init1() 29 { 30 memset(head,-1,sizeof(head)); 31 memset(vis,0,sizeof(vis)); 32 fill(dis1,dis1+maxn,inf); 33 cnt=0; 34 } 35 void init2() 36 { 37 cnt=0; 38 memset(head,sizeof(head)); 39 memset(vis,sizeof(vis)); 40 fill(dis2,dis2+maxn,inf); 41 } 42 void add(int x,int y,long long w) 43 { 44 e[cnt].to=y; 45 e[cnt].w=w; 46 e[cnt].next=head[x]; 47 head[x]=cnt++; 48 } 49 void dijkstra(int sx) 50 { 51 priority_queue<node> q; 52 q.push(node(sx,0)); 53 dis1[sx]=0; 54 while(!q.empty()) 55 { 56 node u=q.top(); 57 q.pop(); 58 if(vis[u.pos]) 59 continue; 60 vis[u.pos]=1; 61 for(int i=head[u.pos];i!=-1;i=e[i].next) 62 { 63 int v=e[i].to; 64 if(dis1[v]>dis1[u.pos]+e[i].w) 65 { 66 dis1[v]=dis1[u.pos]+e[i].w; 67 q.push(node(v,dis1[v])); 68 } 69 } 70 } 71 } 72 void dijkstra2(int sx) 73 { 74 priority_queue<node> q; 75 q.push(node(sx,0)); 76 dis2[sx]=0; 77 while(!q.empty()) 78 { 79 node u=q.top();q.pop(); 80 if(vis[u.pos]) 81 continue; 82
83 vis[u.pos]=1; 84 for(int i=head[u.pos];i!=-1;i=e[i].next) 85 { 86 int v=e[i].to; 87 if(dis2[v]>dis2[u.pos]+e[i].w) 88 { 89 dis2[v]=dis2[u.pos]+e[i].w; 90 q.push(node(v,dis2[v])); 91 } 92 } 93 } 94 } 95 int u[maxn],v[maxn]; 96 long long wei[maxn]; 97 string a,b; 98 int main() 99 { 100 int sx,ex; 101 int n,m; 102 while(~scanf("%d%d",&n,&m)) 103 { 104 init1(); 105 int id=0; 106 map<string,int >mp; 107 for(int i=1;i<=m;i++) 108 { 109 cin>>a>>b>>wei[i]; 110 if(!mp.count(a)) 111 mp[a]=id++; 112 if(!mp.count(b)) 113 mp[b]=id++; 114 u[i]=mp[a]; 115 v[i]=mp[b]; 116 add(u[i],v[i],wei[i]); 117 } 118 cin>>a>>b; 119 if(!mp.count(a)) 120 mp[a]=id++; 121 if(!mp.count(b)) 122 mp[b]=id++; 123 sx=mp[a]; 124 ex=mp[b]; 125 dijkstra(sx); 126 if(dis1[ex]==inf) 127 { 128 printf("-1n"); 129 } 130 else
131 { 132 long long ans=inf; 133 init2(); 134 for(int i=1;i<=m;i++) 135 { 136 add(v[i],u[i],wei[i]); 137 } 138 dijkstra2(ex); 139 for(int i=1;i<=m;i++) 140 { 141 ans=min(ans,dis1[u[i]]+dis2[v[i]]+wei[i]/2); 142 } 143 cout<<ans<<endl; 144 } 145 } 146 return 0; 147 }
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |