Flight

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 5058 Accepted Submission(s): 1146

Problem Description
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

题意：求两个点之间的最短路，可以选择某一次的路径权值减半，求这两个点之间最小的权值。

一般有两种方法解决分层图最短路问题：
1 . 建图时直接建成k+1层。
2 . 多开一维记录机会信息。

我个人常用第二种写法：

我们把dis数组和vis数组多开一维记录k次机会的信息。

dis[ i ][ j ] 代表到达 i 用了 j 次免费机会的最小花费.
vis[ i ][ j ] 代表到达 i 用了 j 次免费机会的情况是否出现过.

更新的时候先更新同层之间（即花费免费机会相同）的最短路，然后更新从该层到下一层（即再花费一次免费机会）的最短路。

不使用机会 dis[v][c] = min（min，dis[now][c] + edge[i].w）;
使用机会 dis[v][c+1] = min（dis[v][c+1]，dis[now][c]）;

ac代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10;
int n,m,tot,cnt,head[N];
ll dst[N][2];
unordered_map<string,int> mp;
string a,b;
struct node
{
	int to,w,next;
}t[N*5];
void add(int u,int v,int w)
{
	t[tot].to=v; t[tot].w=w; t[tot].next=head[u]; head[u]=tot++;
}
void spfa()
{
	int isqueue[N][2]={0};	isqueue[mp[a]][0]=1;
	memset(dst,0x3f,sizeof dst);	dst[mp[a]][0]=0;
	queue<pair<int,int> > q;	q.push({mp[a],0});
	while(q.size())
	{
		pair<int,int> u=q.front();	q.pop();
		int u1=u.first;	int u2=u.second;	isqueue[u1][u2]=0;//一个记录当前的点，一个记录用了几次
		for(int i=head[u1];~i;i=t[i].next)
		{
			int w=t[i].w;	int v=t[i].to;
			for(int j=0;j<=1;j++)//当前使用了0 到 k 次减半权值 ，也就是0 到 1
			{
				if(dst[v][j]>dst[u1][j]+w)
				{
					dst[v][j]=dst[u1][j]+w;
					if(!isqueue[v][j])	isqueue[v][j]=1,q.push({v,j});
				}
				if(j&&dst[v][j]>dst[u1][j-1]+w/2)
				{
					dst[v][j]=dst[u1][j-1]+w/2;
					if(!isqueue[v][j])	isqueue[v][j]=1,q.push({v,j});
				}
			}
		}
	}
}
int main()
{
	while(cin>>n>>m)
	{
		tot=cnt=0;	memset(head,-1,sizeof head);	mp.clear();
		while(m--)
		{
			int w;	cin>>a>>b>>w;
			if(!mp[a])	mp[a]=++cnt;
			if(!mp[b])	mp[b]=++cnt;
			add(mp[a],mp[b],w);
		}
		cin>>a>>b;
		if(!mp[a])	mp[a]=++cnt;
		if(!mp[b])	mp[b]=++cnt;
		spfa();
		ll res=inf;
		res=min(dst[mp[b]][1],dst[mp[b]][0]);
		if(res==inf)	res=-1;
		cout<<res<<endl;
	}
	return 0;
}