HDU 3499 Flight(分层图最短路)

#include <bits/stdc++.h>
#define maxn 100005 << 1
#define maxm 500005 << 2
#define ll long long
const ll inf = 0x3f3f3f3f3f3f3f3f;
using namespace std;
struct Node{
	int to, next, w;
	bool operator < (const Node &a) const{
		return a.w < w;
	}
}Edge[maxm], Now, Next;
int head[maxn],num;
ll dist[maxn];
bool vis[maxn];
int n,m;

void init(){
	for(int i=0;i<=n*2;i++) head[i] = -1;
	num = 0;
}

void add(int u,int v,int w){
	Edge[num].to = v;
	Edge[num].w = w;
	Edge[num].next = head[u];
	head[u] = num ++;
}

void dijkstra(int s){
	for(int i=0;i<=2*n;i++){
		dist[i] = inf;
		vis[i] = false;
	}
	dist[s] = 0;
	priority_queue<Node> q;
	Now.to = s;
	q.push(Now);
	while(!q.empty()){
		int u = q.top().to;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i=head[u];i!=-1;i=Edge[i].next){
			int v = Edge[i].to;
			if(!vis[v] && dist[v] > dist[u] + Edge[i].w){
				dist[v] = dist[u] + Edge[i].w;
				Next.to = v;
				Next.w = dist[v];
				q.push(Next);
			}
		}
	}
}

int main()
{
	while(~scanf("%d%d",&n,&m)){
		init();
		map<string,int> ma;
		int pos = 1;
		int w;
		char u[15],v[15],s[15],t[15];
		for(int i=0;i<m;i++){
			scanf("%s%s%d",u,v,&w);
			if(!ma[u]) ma[u] = pos ++;
			if(!ma[v]) ma[v] = pos ++;
			add(ma[u], ma[v], w);
			add(ma[u] + n, ma[v] + n, w);
			add(ma[u], ma[v] + n, w / 2);
		}
		scanf("%s%s",s,t);
		if( !ma[s] || !ma[t]){
			puts("-1");
			continue;
		}
		dijkstra(ma[s]);
		printf("%lld\n", dist[ma[t] + n] == inf ? -1 : dist[ma[t] + n]);
	}
	return 0;
}