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? Input There are no more than 10 test cases. Subsequent test cases are separated by a blank line. The first line of each test case contains two integers N and M ( 2 <= N <= 100,000 0 <= M <= 500,000 ), representing the number of cities and flights. Each of the following M lines contains "X Y D" representing a flight from city X to city Y with ticket price D ( 1 <= D <= 100,000 ). Notice that not all of the cities will appear in the list! The last line contains "S E" representing the start and end city. X, Y, S, E are all strings consisting of at most 10 alphanumeric characters. Output One line for each test case the least money Shua Shua have to pay. If it's impossible for him to finish the trip, just output -1. Sample Input 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.  首先要知道这条如果让一条原本是最短路径(假设总距离为x)上最长的边变成半价，最终求得的解不一定是最优的。 我一开始想成先求出最短路径，然后，把最短路径里面最长的那条路减半不就好了么，事实就是如果减半的话，最短路径就可能不再是这条路。   很 明显必须从m条边中枚举那条半价的航班.假设这条半价的航班是i->j的.那么我们必须知道从A到i的最短距离和从j到B的最短距离. 从A到i的最短距离可以通过求A的单源最短路径即可.从j(j有可能是任意点)到B的最短距离必须建立原图的反向图,然后求B到其他所有点的单源最短路径.(想想是不是)。 以上转载自：http://blog.csdn.net/u013480600/article/details/37884507

 我当时有疑惑的地方：

1.边数太多，采用邻接表存储，不知道怎样去重。

2.当时思路错误想着，存储下来路径，然后就不会了。

3.代码重复量太大

解答：1.不需要去重，有放在那里就好。想一想，这些重边都是有一个相同的起点和终点，假如我们先是拿的短的

来松弛，好现在松弛完了，如果在拿来另一条同起同终的边，但是权值大了，我们再去松弛，你能松弛么，明显

dis[v]<dis[u]+w,所以根本不符合判断条件，自动舍弃。同理我们先拿来同起同终的长边，再拿来短边，我们还是满足松弛条件的，自然会松弛。

     3.新学习一种结构体，我们把相应的变量和函数都放在这里面，只要换一个变量名就好了。

原始加长版：

#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> #include<map> #include<queue> #define INF 1e18 using namespace std; typedef long long ll; int n,m; map<string,int> flight; int cnt1,cnt2; int st,ed; ll dis1[100010],dis2[100010]; int vis[100010]; struct edge//枚举边 { int u,v; int w; }Edge[500010]; /* 这种结构超级麻烦，一会看一下，别人的代码 */ struct edge1 { int v,w; int next; }Edge1[500010]; int head1[100010]; void add_edge1(int u,int v,int w)//建立正边 { Edge1[cnt1].v=v,Edge1[cnt1].w=w; Edge1[cnt1].next=head1[u]; head1[u]=cnt1++; } struct edge2 { int v,w; int next; }Edge2[500010]; int head2[500010]; void add_edge2(int u,int v,int w)//建立反向边 { Edge2[cnt2].v=v,Edge2[cnt2].w=w; Edge2[cnt2].next=head2[u]; head2[u]=cnt2++; } void spfa1(int st) { for(int i=1;i<=n;i++) dis1[i]=INF; memset(vis,0,sizeof(vis)); dis1[st]=0;//自己距离自己是0 queue<int> q; q.push(st); vis[st]=1; while(q.size()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head1[now];i!=-1;i=Edge1[i].next) { int v=Edge1[i].v,w=Edge1[i].w; if(dis1[v]>dis1[now]+w) { dis1[v]=dis1[now]+w; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } void spfa2(int ed) { for(int i=1;i<=n;i++) dis2[i]=INF; memset(vis,0,sizeof(vis)); dis2[ed]=0; queue<int> q; q.push(ed); vis[ed]=1; while(q.size()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head2[now];i!=-1;i=Edge2[i].next) { int v=Edge2[i].v,w=Edge2[i].w; if(dis2[v]>dis2[now]+w) { dis2[v]=dis2[now]+w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { while(~scanf("%d %d",&n,&m)) { cnt1=cnt2=0;//太冗长了 memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); memset(Edge,0,sizeof(Edge)); memset(Edge1,0,sizeof(Edge1)); memset(Edge2,0,sizeof(Edge2)); for(int i=0;i<=n;i++) flight.clear(); string a,b;int w; int it=1; for(int i=0;i<m;i++) { cin>>a>>b>>w; if(!flight[a])//对地名进行标号 flight[a]=it++; if(!flight[b]) flight[b]=it++; Edge[i].u=flight[a],Edge[i].v=flight[b],Edge[i].w=w;//对边进行记录 add_edge1(flight[a],flight[b],w);//添加边，利于后面的遍历 add_edge2(flight[b],flight[a],w); } cin>>a>>b; if(!flight[a]) flight[a]=it++; if(!flight[b]) flight[b]=it++; st=flight[a],ed=flight[b]; spfa1(st);//正向找到距离，也就是正向建图 spfa2(ed);//反向建图找到距离 ll ans=INF; for(int i=0;i<m;i++) { int one,two,val; one=Edge[i].u,two=Edge[i].v; val=Edge[i].w; if(dis1[one]+dis2[two]+val/2<ans) ans=dis1[one]+dis2[two]+val/2; } if(ans!=INF) printf("%I64d\n",ans); else printf("-1\n"); } return 0; } 精简版

#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> #include<map> #include<queue> #define INF 1e18 using namespace std; typedef long long ll; /* 就是建立一个结构体，然后将关于他的函数，都封装在这个结构体里面， 这样的话，只需要建立一个结构体，我们就不用来重复大量的代码 */ int n,m; struct edge//枚举边 { int u,v; int w; }Edge[500010]; map<string,int> flight; int st,ed; struct s//把相关的量都封装在这个结构体里面，包括函数，才发现，她竟然还能装函数，666 { int cnt; ll dis[100010]; int vis[100010]; struct edge { int v,w; int next; }Edge[500010]; int head[100010]; void add_edge(int u,int v,int w)//建立正边 { Edge[cnt].v=v,Edge[cnt].w=w; Edge[cnt].next=head[u]; head[u]=cnt++; } void spfa(int st) { for(int i=1;i<=n;i++) dis[i]=INF; memset(vis,0,sizeof(vis)); dis[st]=0;//自己距离自己是0 queue<int> q; q.push(st); vis[st]=1; while(q.size()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head[now];i!=-1;i=Edge[i].next) { int v=Edge[i].v,w=Edge[i].w; if(dis[v]>dis[now]+w) { dis[v]=dis[now]+w; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } }s1,s2; int main() { while(~scanf("%d %d",&n,&m)) { s1.cnt=s2.cnt=0; memset(Edge,0,sizeof(Edge)); memset(s1.Edge,0,sizeof(s1.Edge)),memset(s2.Edge,0,sizeof(s2.Edge)); memset(s1.head,-1,sizeof(s1.head)), memset(s2.head,-1,sizeof(s2.head)); for(int i=0;i<=n;i++) flight.clear(); string a,b;int w; int it=1; for(int i=0;i<m;i++) { cin>>a>>b>>w; if(!flight[a])//对地名进行标号 flight[a]=it++; if(!flight[b]) flight[b]=it++; Edge[i].u=flight[a],Edge[i].v=flight[b],Edge[i].w=w;//对边进行记录 s1.add_edge(flight[a],flight[b],w);//添加边，利于后面的遍历 s2.add_edge(flight[b],flight[a],w); } cin>>a>>b; if(!flight[a]) flight[a]=it++; if(!flight[b]) flight[b]=it++; st=flight[a],ed=flight[b]; s1.spfa(st);//正向找到距离，也就是正向建图 s2.spfa(ed);//反向建图找到距离 ll ans=INF; for(int i=0;i<m;i++) { int one,two,val; one=Edge[i].u,two=Edge[i].v; val=Edge[i].w; if(s1.dis[one]+s2.dis[two]+val/2<ans) ans=s1.dis[one]+s2.dis[two]+val/2; } if(ans!=INF) printf("%I64d\n",ans); else printf("-1\n"); } return 0; }