「JoyOI1467」通向聚会的道路
背景 Background
Candy住在一个被划分为n个区域的神奇小镇中，其中Candy的家在编号为n的区域，Candy生日这天，大家都急急忙忙赶去Candy家庆祝Candy的生日。
描述 Description
Candy共有t个朋友住在不同的区域。小镇有m条道路，小镇的神奇之处在于其中的p1条道路只会在你走过区域的的个数为奇数时候开启，p2道路只会在你走过区域的个数为偶数的时候开启，剩下的道路一直都会开启。并且，所有的道路只能够单向通过。飘飘乎居士希望知道在所有的好朋友中，谁离Candy最近?。
输入格式 InputFormat
第一行：两个正整数n m，表示共n个区域，m条道路
接下来m行，每行三个正整数u v s表示u到v的单向道路，路程为s，其中第i条道路的编号为i。
接着一个整数p1以及p1个正整数odd[i]，表示编号为odd[i]的道路只会在走过奇数个区域时开启。
接着一个整数p2以及p2个正整数even[i]，表示编号为even[i]的道路只会在走过偶数个区域时开启。
接下来一个正整数 t
紧接着t行，每行一个正整数h以及一个不超过10个字符长度的字符串na（且均有小写字母组成），表示在h区域居住着名字为na的人。
输出格式 OutputFormat
第一行，即距离candy家最近的人的名字，数据保证有且只有一个人为最后的答案。
第二行，该人到candy家的距离。
如果存在多解，则输入名字中字典序较小的一人。
数据范围和注释 Hint
pink尽管从1->3->4距离更近，但因为1->2的这条道路只有在走过奇数个区域时才开启，而pink此时走过的区域为偶数个（0个）（我们规定，出发点不算走第一个区域），所以pink只好沿1—>2—>3—>4，距离为5；
Violethill尽管沿2—>3—>4距离为3，但因为3—>4这条道路只有在走过偶数个区域时才开启，当violethill从2到3时，只走了奇数个（1个）区域，道路不会开启。所以，violethill只好沿2—>4这条道路行走，距离为4，所以violethill比pink更快到candy家中，并且距离为4。
对于30%的数据 0<n<=100
对于100%的数据0<n<=10000 0<m<=100000
对于所有数据保证两区域间的距离<=100000
数据保证运算即结果在maxlongint以内
数据保证输入的正确性，即至少有一个人可以到达candy家中，并且一个区域最多只有一人，不会出现相同名字的人。
友情提示：可能出现有些道路既在odd中出现，也在even中出现。并且odd或者even中的数都可能出现重复数字。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; struct data{int to,next,v;}e[200001]; int n,m,p1,p2,cnt,head[20001],q[20001],dis[20001]; int x[100001],y[100001],z[100001]; bool odd[100001],even[100001],inq[20001]; int tot,pos[10001];char name[10001][20]; void ins(int v,int u,int w) {e[++cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void build() { for(int i=1;i<=m;i++) { if(odd[i])ins(x[i]+n,y[i],z[i]); if(even[i])ins(x[i],y[i]+n,z[i]); if((odd[i]|even[i])==0) { ins(x[i]+n,y[i],z[i]); ins(x[i],y[i]+n,z[i]); } } } void spfa() { int t=0,w=0,i,now; memset(dis,127/3,sizeof(dis)); q[w++]=n;q[w++]=n+n; inq[n]=1;inq[n+n]=1; dis[n]=0;dis[n+n]=0; while(t!=w) { now=q[t];t++;i=head[now]; if(t==20001)t=0; while(i) { if(dis[now]+e[i].v<dis[e[i].to]) { dis[e[i].to]=dis[now]+e[i].v; if(!inq[e[i].to]) { inq[e[i].to]=1; q[w++]=e[i].to; if(w==20001)w=0; } } i=e[i].next; } inq[now]=0; } } void work() { int ans=0x7fffffff;char ch[20]; for(int i=1;i<=tot;i++) { if(dis[pos[i]]<ans) { ans=dis[pos[i]]; memcpy(ch,name[i],sizeof(name[i])); } else if(dis[pos[i]]==ans) { if(ch>name[i]) memcpy(ch,name[i],sizeof(name[i])); } } printf("%s\n%d",ch,ans); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]); int temp; scanf("%d",&p1); for(int i=1;i<=p1;i++){scanf("%d",&temp);odd[temp]=1;} scanf("%d",&p2); for(int i=1;i<=p2;i++){scanf("%d",&temp);even[temp]=1;} scanf("%d",&tot); for(int i=1;i<=tot;i++) scanf("%d%s",&pos[i],name[i]); build(); spfa(); work(); return 0; } |
OI 课件=>
