记录编号	346525	评测结果	AAAAAAAAAA
题目名称	通向聚会的套路	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	1.099 s
提交时间	2016-11-12 10:08:56	内存使用	2.03 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define LL long long
#define Inf 1e9+7
const int maxn=10000+2;
struct Node{
	int num,dis,type;
	Node(){};
	Node(int a,int b,int c){num=a;dis=b;type=c;}
	bool operator < (const Node & a)const{
		return dis>a.dis;
	}
};
struct Peo{
	string name;
	int pos;
	bool operator < (const Peo & a)const{
		return name<a.name;
	}
}peo[maxn];
struct Edge{
	int next,to,dis,num;
}e[maxn*10];
int n,m,len,head[maxn];
bool odd[maxn*10],even[maxn*10];
int dis[maxn][3];
void Insert(int x,int y,int z,int num){
	len++;e[len].num=num;
	e[len].to=y;e[len].next=head[x];
	e[len].dis=z;head[x]=len;
}
int Dijs(int x){
	memset(dis,0x3f,sizeof(dis));dis[x][1]=dis[x][0]=0;
	bool f[maxn][3]={0};memset(f,0,sizeof(f));f[x][0]=f[x][0]=1;
	priority_queue<Node> q;q.push(Node(x,dis[x][0],0));q.push(Node(x,dis[x][1],1));
	while(!q.empty()){
		Node temp=q.top();q.pop();
		int k=temp.num,type=temp.type;f[k][type]=true;
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(odd[e[i].num] && even[e[i].num])odd[e[i].num]=false,even[e[i].num]=false;
			if(odd[e[i].num] && type==1)continue;
			if(even[e[i].num] && type==0)continue;
			if(!f[j][!type] && dis[j][!type]>dis[k][type]+e[i].dis){
				dis[j][!type]=dis[k][type]+e[i].dis;
				q.push(Node(j,dis[j][!type],!type));
			}
		}
	}
}
void Init();
/*
7 9
1 2 1
2 7 10
2 7 11
2 3 1
3 4 1
4 2 1
2 7 1
5 7 100
6 7 101
1 2
1 7
3
5 rooney
6 giggs
1 scholes
*/
int main(){
	freopen("party_ezoi.in","r",stdin);
	freopen("party_ezoi.out","w",stdout);
    Init();
    //for(;;);
    getchar();getchar();
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Insert(y,x,z,i);
	}
	int K;
	scanf("%d",&K);
	for(int i=1,x;i<=K;i++){
		scanf("%d",&x);odd[x]=true;//只在奇数时开启
	}
	scanf("%d",&K);
	for(int i=1,x;i<=K;i++){
		scanf("%d",&x);
		even[x]=true;//只在偶数时开启
	}
	for(int i=1;i<=m;i++){
		if(even[i] && odd[i]){even[i]=odd[i]=0;}
	}
	Dijs(n);
	scanf("%d",&K);
	for(int i=1;i<=K;i++){
		char s[maxn];scanf("%d%s",&peo[i].pos,s);
		peo[i].name=s;
	}
	sort(peo+1,peo+K+1);
	string ansname;int ansdis=2e9;
	for(int i=1;i<=K;i++){
		int now=dis[peo[i].pos][0];
		if(ansdis>now){
			ansdis=now;ansname=peo[i].name;
		}
	}
	cout<<ansname<<endl<<ansdis;
}
/*
4 5
1 2 2
3 4 2
2 4 4
1 3 1
2 3 1
1 4
1 2
2
2 violethill
1 pink
*/