背景

??Candy住在一個被劃分為n個區(qū)域的神奇小鎮(zhèn)中，其中Candy的家在編號為n的區(qū)域，Candy生日這天，大家都急急忙忙趕去Candy家慶祝Candy的生日。

描述

??Candy共有t個朋友住在不同的區(qū)域。小鎮(zhèn)有m條道路，小鎮(zhèn)的神奇之處在于其中的p1條道路只會在你走過區(qū)域的的個數(shù)為奇數(shù)時候開啟，p2道路只會在你走過區(qū)域的個數(shù)為偶數(shù)的時候開啟，剩下的道路一直都會開啟。并且，所有的道路只能夠單向通過。飄飄乎居士希望知道在所有的好朋友中，誰離Candy最近?。

輸入格式

第一行：兩個正整數(shù)n?m，表示共n個區(qū)域，m條道路
接下來m行，每行三個正整數(shù)u?v?s表示u到v的單向道路，路程為s，其中第i條道路的編號為i。
接著一個整數(shù)p1以及p1個正整數(shù)odd[i]，表示編號為odd[i]的道路只會在走過奇數(shù)個區(qū)域時開啟。
接著一個整數(shù)p2以及p2個正整數(shù)even[i]，表示編號為even[i]的道路只會在走過偶數(shù)個區(qū)域時開啟。
接下來一個正整數(shù)?t
緊接著t行，每行一個正整數(shù)h以及一個不超過10個字符長度的字符串na（且均有小寫字母組成），表示在h區(qū)域居住著名字為na的人。

輸出格式

第一行，即距離candy家最近的人的名字，數(shù)據(jù)保證有且只有一個人為最后的答案。??????
第二行，該人到candy家的距離。
????????如果存在多解，則輸入名字中字典序較小的一人。

測試樣例1

輸入

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?

輸出

violethill?
4

備注

pink盡管從1->3->4距離更近，但因為1->2的這條道路只有在走過奇數(shù)個區(qū)域時才開啟，而pink此時走過的區(qū)域為偶數(shù)個（0個）（我們規(guī)定，出發(fā)點不算走第一個區(qū)域），所以pink只好沿1—>2—>3—>4，距離為5；
Violethill盡管沿2—>3—>4距離為3，但因為3—>4這條道路只有在走過偶數(shù)個區(qū)域時才開啟，當violethill從2到3時，只走了奇數(shù)個（1個）區(qū)域，道路不會開啟。所以，violethill只好沿2—>4這條道路行走，距離為4，所以violethill比pink更快到candy家中，并且距離為4。
對于30%的數(shù)據(jù)?0<n<=100
對于100%的數(shù)據(jù)0<n<=10000???0<m<=100000
對于所有數(shù)據(jù)保證兩區(qū)域間的距離<=100000
數(shù)據(jù)保證運算即結(jié)果在maxlongint以內(nèi)
數(shù)據(jù)保證輸入的正確性，即至少有一個人可以到達candy家中，并且一個區(qū)域最多只有一人，不會出現(xiàn)相同名字的人。
友情提示：可能出現(xiàn)有些道路既在odd中出現(xiàn)，也在even中出現(xiàn)。并且odd或者even中的數(shù)都可能出現(xiàn)重復數(shù)字。 題目有毒！！！可能出現(xiàn)有些道路既在odd中出現(xiàn)，也在even中出現(xiàn)，意思是一直開啟而不是由于條件矛盾而都不開啟。 由于這個我一直WA三個點還以為自己又犯了什么智障錯誤要寫手打堆了呢。。。 我們把有奇數(shù)限制的邊叫為奇邊，有偶數(shù)限制的邊叫為偶邊，沒有限制（既在odd中出現(xiàn)，也在even中出現(xiàn)或都沒出現(xiàn)）的邊拆成一條奇邊和一條偶邊。 我們把每個區(qū)域分成兩個點，一個為入邊為奇邊，出邊為偶邊的，一個為入邊為偶邊，出邊為奇邊的，然后反向建圖spfa。 //Serene #include<algorithm> #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; #define ull unsigned long long const int maxn=2e4+10,maxm=2e5+10; const ull INF=-1; int n,m; int mu[maxm],mv[maxm]; ull ms[maxm],ans=INF; bool modd[maxm],meven[maxm];ull aa;char cc; ull read() {aa=0;cc=getchar();while(cc<'0'||cc>'9') cc=getchar();while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();return aa; }struct Pp{int x;string s; }pp[maxn];bool cmp(const Pp &a,const Pp &b) {return a.s<b.s; }int fir[maxn],nxt[maxm],to[maxm],e=0;ull v[maxm]; void add(int y,int x,int z) {to[++e]=y;nxt[e]=fir[x];fir[x]=e;v[e]=z; }ull dis[maxn]; int zz[maxn]; bool vis[maxn]; void spfa(int st){memset(dis,-1,sizeof(dis));int s=1,t=0,x,y,z;dis[st]=0;zz[++t]=st;vis[st]=1;while(s<=t) {x=zz[s%maxn];s++;vis[x]=0;for(y=fir[x];y;y=nxt[y]) {z=to[y];if(dis[z]<=dis[x]||dis[z]<=dis[x]+v[y]) continue;dis[z]=dis[x]+v[y];if(!vis[z]) {vis[z]=1;t++;zz[t%maxn]=z;}}} }int main() {n=read();m=read();for(int i=1;i<=m;++i) {mu[i]=read();mv[i]=read();ms[i]=read();}int x=read(),y;for(int i=1;i<=x;++i) {y=read();modd[y]=1;}x=read();for(int i=1;i<=x;++i) {y=read();meven[y]=1;}for(int i=1;i<=m;++i) {if(!modd[i]) add(mu[i],mv[i]+n,ms[i]);if(!meven[i]) add(mu[i]+n,mv[i],ms[i]);if(modd[i]&&meven[i]) {add(mu[i]+n,mv[i],ms[i]);add(mu[i],mv[i]+n,ms[i]);}}add(n,2*n+1,0);add(2*n,2*n+1,0);x=read();for(int i=1;i<=x;++i) {pp[i].x=read();cin>>pp[i].s;}sort(pp+1,pp+x+1,cmp);spfa(2*n+1);y=0;for(int i=1;i<=x;++i) {if(dis[pp[i].x]<ans) {y=i;ans=dis[pp[i].x];}}cout<<pp[y].s<<"\n";cout<<ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Serene-shixinyi/p/7531821.html

總結(jié)

以上是生活随笔為你收集整理的tyvj1467 通向聚会的道路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。