「tyvj1467-road」通向聚会的道路 - 分层图

题目大意

candy共有t个朋友住在不同的区域。小镇有m条道路，小镇的神奇之处在于其中的p1条道路只会在你走过区域的的个数为奇数时候开启，p2道路只会在你走过区域的个数为偶数的时候开启，剩下的道路一直都会开启。并且，所有的道路只能够单向通过。飘飘乎居士希望知道在所有的好朋友中，谁离candy最近。

---

题目分析

显然我们可以修改Spfa的$dist[]$为二维数组$dist[i][0/1]$分别表示到达$i$时是经过奇数点还是偶数点进行更新。
从$n$开始建反图跑Spfa，因为建了反图，因此转移的时候实际上是经过偶数个点的时候走奇数边到达下一个点。
为什么呢？因为状态的定义是到达$i$时，而这是反图因此当前边尚不存在。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=10005;
int n,m,k,dist[maxn][2],inque[maxn],ans=0x7fffffff/2;
string Name;
struct Edge {
	int from,to,dist,bj;
} edge[10*maxn];
vector<Edge>edges[maxn];
void AddEdge(const Edge& e) {
	edges[e.from].push_back(e);
}
void Spfa(int s) {
	memset(dist,0x3f,sizeof(dist));
	dist[s][1]=dist[s][0]=0;
	inque[s]=1;
	queue<int>Q; 
	Q.push(s);
	while(!Q.empty()) {
		int Now=Q.front();
		Q.pop();
		inque[Now]=0;
		for(Edge& e:edges[Now]) {
			int Next=e.to;
			if(e.bj!=2) { //奇边 
				if(dist[Next][0]>dist[Now][1]+e.dist) {
					dist[Next][0]=dist[Now][1]+e.dist;
					if(!inque[Next]) {
						inque[Next]=1;
						Q.push(Next);
					}
				}
			}
			if(e.bj!=1) { //偶边 
				if(dist[Next][1]>dist[Now][0]+e.dist) {
					dist[Next][1]=dist[Now][0]+e.dist;
					if(!inque[Next]) {
						inque[Next]=1;
						Q.push(Next);
					}
				}
			}
		}
	}
}
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=m; i++) {
		int x=Get_Int(),y=Get_Int(),v=Get_Int();
		edge[i]=(Edge) {y,x,v};
	}
	int tmp=Get_Int();
	for(int i=1; i<=tmp; i++)edge[Get_Int()].bj++;
	tmp=Get_Int();
	for(int i=1; i<=tmp; i++)edge[Get_Int()].bj+=2;
	for(int i=1; i<=m; i++)AddEdge(edge[i]);
	Spfa(n);
	k=Get_Int();
	for(int i=1; i<=k; i++) {
		int x=Get_Int();
		char s[25];
		scanf("%s",s);
		string name=s;
		if(ans>dist[x][1]||(ans==dist[x][1]&&name<Name)) {
			ans=dist[x][1];
			Name=name;
		}
	}
	cout<<Name<<endl<<ans<<endl;
	return 0;
}