公司做网站会计分录,0wordpress tint-k主题,WordPress单栏二次元主题,做网站联系方式腾讯大战360
题目大意#xff1a;
有n个点#xff0c;还有m条线连接着这些点#xff0c;有两个人在其中两个点上#xff0c;让这两个人相遇最快要多久
原题#xff1a;
题目描述
2010年11月3日#xff0c;是一个难忘的日子。 腾讯发布消息#xff1a;存360则#…腾讯大战360
题目大意
有n个点还有m条线连接着这些点有两个人在其中两个点上让这两个人相遇最快要多久
原题
题目描述
2010年11月3日是一个难忘的日子。 腾讯发布消息存360则不留QQ。留QQ则须卸360。 360则表示360与QQ可以共存。 这也就标志着腾讯与360的大战就此开始 现在腾讯与360由于身处异地非常迫切地想在最短的时间内相遇然后干一架。但是由于双方的技术员都在努力地编程序想干掉对方所以他们希望你来帮他们找到一个最好的方案使得相遇的时间最短。 在此我们定义“相遇”为两个人皆在同一个有编号的城市上就可以了并且这两个人均可以站在原地等另外一个人。也就是说在这里我们不考虑两人在路中间相遇。
输入
输入数据第一行N和M用空格隔开 表示这是一个N*N的图并且有M条边,第二行到第M1行 为这个图的详细信息。 每行共有被空格隔开的三个数a b c。表示编号为a的城市到编号为b的城市 有一个双向边并且要过这条双向边所需要花费的时间为c。 最后一行有两个数S和TS表示腾讯所处的城市也就是深圳T表示360所处的 城市也就是北京
输出
输出只有一行D表示二者“相遇”的最短时间。当然如果无法相遇则输出“Peace!”
输入样例
3 3
1 2 1
2 3 1
1 3 1
1 3输出样例
1说明
[数据范围]每组都是n5000 m5000 并且保证运算过程中的所有值都不会超过117901063
解题思路
两次SPFA找一个相遇点连接并求最小就可以了
代码
#includecstdio
#includeiostream
#includecstring
#includequeue
using namespace std;
int n,m,x,y,c,now,w,ans,t,b[5005],p[5005],bb[5005],head[5005];
struct rec
{int to,l,next;
}a[10005];
int main()
{scanf(%d %d,n,m);for (int i1;im;i){scanf(%d %d %d,x,y,c);a[w].toy;//无向a[w].lc;a[w].nexthead[x];head[x]w;a[w].tox;a[w].lc;a[w].nexthead[y];head[y]w;}scanf(%d %d,x,y);memset(b,127/3,sizeof(b));tb[1];queueintd;d.push(x);b[x]0;//清零p[x]1;while (!d.empty())//第一次SPFA{nowd.front();d.pop();for (int ihead[now];i;ia[i].next)if (b[now]a[i].lb[a[i].to]){b[a[i].to]b[now]a[i].l;if (!p[a[i].to]){p[a[i].to]1;d.push(a[i].to);}}p[now]0;}memset(bb,127/3,sizeof(bb));d.push(y);bb[y]0;p[y]1;while (!d.empty())//第二次SPFA{nowd.front();d.pop();for (int ihead[now];i;ia[i].next)if (bb[now]a[i].lbb[a[i].to]){bb[a[i].to]bb[now]a[i].l;if (!p[a[i].to]){p[a[i].to]1;d.push(a[i].to);}}p[now]0;}ans2147483647;for (int i1;in;i)//枚举点ansmin(ans,max(b[i],bb[i]));//求最优的if(anst||ans2147483647) printf(Peace!);//无法到达else printf(%d,ans);//输出
}
