HDU-3499:Flight（SPFA+dp）

太阳不下山

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
概译：共有N个城市，M行里给出某市到另一个市（单向）的机票价格（这M行未必包含所有的N个城市），然后给出起始点和终点。这期间可以有一次机票打折机会，求解最小花费。如果到达不了，输出-1。思路：显然的图题。如果没有打折这一条件的话就是有向图的最短路径，而打折条件是典型的、在每一步操作中可选可不选的条件类型，dp处理一下。也就是我们在求解最短路的过程中加上几条dp思想的语句来记录所需结果，此处最短路用的是spfa。另外注意一下这个题中，点的给出形式为字符串，我用的是STL中的map对其进行转化处理。代码如下：

1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 #include<map>
 6 #include<vector>
 7 #include<climits>
 8 using namespace std;
 9 
10 typedef long long ll;
11 const long long inf=LLONG_MAX;
12 
13 struct node
14 {
15   int id,cost;
16   node(int x,int y):id(x),cost(y){}
17 };
18 int n,m,cnt;//点数、边数、在输入里出现过的城市数 
19 ll dis[100005][2];//dp处理的距离 
20 bool vis[100005];//spfa里负责记录是否在队列中 
21 char ch1[15],ch2[15];//城市1，城市2
22 //以下为最短路所需容器 
23 map<string,int>mp;
24 vector<node>v[100005];
25 queue<int>q;
26 
27 void spfa(int k)//求最短路 
28 {
29   for(int i=1;i<=n;i++)
30     dis[i][0]=dis[i][1]=inf;
31   dis[k][0]=dis[k][1]=0;
32   //dis[i][0]代表到达i点时以前打过一次折的最小花费，即dis[城市2][0]就是结果，dis[i][1]是到达i点之前一直不打折的花费 
33   memset(vis,false,sizeof(vis));
34   q.push(k);
35   while(!q.empty())
36   {
37     int t=q.front();q.pop();
38     vis[t]=false;
39     for(int i=0;i<v[t].size();i++)
40     {
41       node e=v[t][i];
42       bool flag=false;
43       if(dis[e.id][1]>dis[t][1]+e.cost)//常规操作，把dis[i][1]当成模板里的dis[i]就行…… 
44       {
45         flag=true;
46         dis[e.id][1]=dis[t][1]+e.cost;
47       }  
48       if(dis[e.id][0]>dis[t][0]+e.cost||dis[e.id][0]>dis[t][1]+e.cost/2)
49       {//dp，之前打了折的花费加上这次的花费，与之前一直不打折这次打折的花费，取最小值为对于这个点的打过一次折以后的最小花费 
50         flag=true;
51         dis[e.id][0]=min(dis[t][0]+e.cost,dis[t][1]+e.cost/2);
52       }
53       if(flag&&!vis[e.id])//更新了花费且此点不在队列中时 
54       {
55         vis[e.id]=true;
56         q.push(e.id);
57       }
58     }  
59   }  
60 }
61 int main()
62 {
63   while(~scanf("%d%d",&n,&m))
64   {
65     //不要忘了各种清空 
66     cnt=0;
67     mp.clear();
68     for(int i=1;i<=n;i++)
69       v[i].clear();
70     //建图 
71     for(int i=1;i<=m;i++)
72     {
73       int cost;//机票钱 
74       scanf("%s%s%d",ch1,ch2,&cost);
75       //如果还没出现过这个城市，加进来，记录下来它的编号，简单起见第几个出现就是几了 
76       if(!mp[ch1]) mp[ch1]=++cnt;
77       if(!mp[ch2]) mp[ch2]=++cnt;
78       v[mp[ch1]].push_back(node(mp[ch2],cost));//单向 
79     }
80     scanf("%s%s",ch1,ch2);//起点终点 
81     if(!mp[ch1]) mp[ch1]=++cnt;
82     if(!mp[ch2]) mp[ch2]=++cnt;
83     spfa(mp[ch1]);//求解 
84     printf("%lld\n",dis[mp[ch2]][0]==inf?-1:dis[mp[ch2]][0]);//inf代表无法到达 
85   }
86   return 0;
87 }