记录编号	313703	评测结果	AAAAAAAAAA
题目名称	通向聚会的套路	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.219 s
提交时间	2016-10-01 21:30:32	内存使用	2.01 MiB

#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 10005;
const int maxm = 100005;
struct Edge{
	int to,next,w,tim;
}G[maxm];
int d[maxn][2],head[maxn],cnt,vis[maxn],q[maxn],r,l,n,m;
void add(int u,int v,int w) {
	G[++cnt].to = v;
	G[cnt].next = head[u];
	head[u] = cnt;
	G[cnt].w = w;
}
#define v G[i].to
#define w G[i].w
void spfa(const int &s){
	memset(d,0x3f,sizeof(d));
	memset(vis,false,sizeof(vis));
	d[s][1] = d[s][0] = r = l = 0;
	vis[s] = true; q[r++] = s;
	while(l != r) {
		int u = q[l++];
		if(l == maxn) l = 0;
		vis[u] = false;
		for(int i = head[u];i;i = G[i].next) {
			if(G[i].tim == 1) {
				if( d[v][0] > d[u][1] + w ) {
					d[v][0] = d[u][1] + w;
					if(!vis[v]){
						vis[v] = true;
						q[r++] = v;
						if(r == maxn) r = 0;
					}
				}
			}else if(G[i].tim==2) {
				if( d[v][1] > d[u][0] + w) {
					d[v][1] = d[u][0] + w;
					if(!vis[v]){
						vis[v] = true;
						q[r++] = v;
						if(r == maxn) r = 0;
					}
				}
			}else{
				if( d[v][1] > d[u][0] + w ) {
					d[v][1] = d[u][0] + w;
					if(!vis[v]){
						vis[v] = true;
						q[r++] = v;
						if(r == maxn) r = 0;
					}
				}
				if( d[v][0] > d[u][1] + w) {
					d[v][0] = d[u][1] + w;
					if(!vis[v]){
						vis[v] = true;
						q[r++] = v;
						if(r == maxn) r = 0;
					}
				}
			}
		}
	}
}
#undef v
#undef w
char s1[30],s2[30];
int main() {
	freopen("party_ezoi.in","r",stdin);
	freopen("party_ezoi.out","w",stdout);
	read(n);read(m);
	int ans = INT_MAX;
	for(int i=1,u,v,w;i<=m;++i){
		read(u);read(v);read(w);
		add(v, u, w);
	}
	int lim;read(lim);
	for(int i=1,x;i<=lim;++i) read(x),++G[x].tim;
	read(lim);
	for(int i=1,x;i<=lim;++i) read(x),(++G[x].tim)++;
	spfa(n);
	read(lim);
	for(int i=1,v;i<=lim;++i){
		read(v);
		scanf("%s", s1);
		if( ans > d[v][1]){
			ans = d[v][1];
			strcpy(s2, s1);
		}
	}
	printf("%s\n%d\n", s2, ans);
	//getchar();getchar();
	return 0;
}