背景

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

描述

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

輸入格式

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

輸出格式

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

測(cè)試樣例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距離更近，但因?yàn)?->2的這條道路只有在走過(guò)奇數(shù)個(gè)區(qū)域時(shí)才開(kāi)啟，而pink此時(shí)走過(guò)的區(qū)域?yàn)榕紨?shù)個(gè)（0個(gè)）（我們規(guī)定，出發(fā)點(diǎn)不算走第一個(gè)區(qū)域），所以pink只好沿1—>2—>3—>4，距離為5；
Violethill盡管沿2—>3—>4距離為3，但因?yàn)?—>4這條道路只有在走過(guò)偶數(shù)個(gè)區(qū)域時(shí)才開(kāi)啟，當(dāng)violethill從2到3時(shí)，只走了奇數(shù)個(gè)（1個(gè)）區(qū)域，道路不會(huì)開(kāi)啟。所以，violethill只好沿2—>4這條道路行走，距離為4，所以violethill比pink更快到candy家中，并且距離為4。
對(duì)于30%的數(shù)據(jù)?0<n<=100
對(duì)于100%的數(shù)據(jù)0<n<=10000???0<m<=100000
對(duì)于所有數(shù)據(jù)保證兩區(qū)域間的距離<=100000
數(shù)據(jù)保證運(yùn)算即結(jié)果在maxlongint以?xún)?nèi)
數(shù)據(jù)保證輸入的正確性，即至少有一個(gè)人可以到達(dá)candy家中，并且一個(gè)區(qū)域最多只有一人，不會(huì)出現(xiàn)相同名字的人。
友情提示：可能出現(xiàn)有些道路既在odd中出現(xiàn)，也在even中出現(xiàn)。并且odd或者even中的數(shù)都可能出現(xiàn)重復(fù)數(shù)字。 題目有毒！！！可能出現(xiàn)有些道路既在odd中出現(xiàn)，也在even中出現(xiàn)，意思是一直開(kāi)啟而不是由于條件矛盾而都不開(kāi)啟。 由于這個(gè)我一直WA三個(gè)點(diǎn)還以為自己又犯了什么智障錯(cuò)誤要寫(xiě)手打堆了呢。。。 我們把有奇數(shù)限制的邊叫為奇邊，有偶數(shù)限制的邊叫為偶邊，沒(méi)有限制（既在odd中出現(xiàn)，也在even中出現(xiàn)或都沒(méi)出現(xiàn)）的邊拆成一條奇邊和一條偶邊。 我們把每個(gè)區(qū)域分成兩個(gè)點(diǎn)，一個(gè)為入邊為奇邊，出邊為偶邊的，一個(gè)為入邊為偶邊，出邊為奇邊的，然后反向建圖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 通向聚会的道路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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