騰訊大戰360

題目

2010年11月3日，是一個難忘的日子。 騰訊發布消息：存360則，不留QQ。留QQ，則須卸360。 360則表示360與QQ可以共存。 這也就標志著騰訊與360的大戰就此開始！
現在，騰訊與360由于身處異地，非常迫切地想在最短的時間內相遇，然后干一架。但是由于雙方的技術員都在努力地編程序想干掉對方，所以他們希望你來幫他們找到一個最好的方案使得相遇的時間最短。
在此我們定義“相遇”為：兩個人皆在同一個有編號的城市上就可以了，并且這兩個人均可以站在原地等另外一個人。也就是說，在這里我們不考慮兩人在路中間相遇。

輸入

輸入數據第一行：N和M（用空格隔開） 表示這是一個N*N的圖并且有M條邊,第二行到第M+1行 為這個圖的詳細信息。
每行共有被空格隔開的三個數：a b c。表示編號為a的城市到編號為b的城市有一個雙向邊，并且要過這條雙向邊所需要花費的時間為c。
最后一行有兩個數：S和T，S表示騰訊所處的城市（也就是深圳），T表示360所處的 城市（也就是北京）

輸出

輸出只有一行，D，表示二者“相遇”的最短時間。當然，如果無法相遇則輸出“Peace!”

輸入樣例

3 3 1 2 1 2 3 1 1 3 1 1 3

輸出樣例

1

數據范圍

每組都是n=5000 m=5000。
保證運算過程中的所有值都不會超過117901063。

思路

這道題呢，可以用兩個地方都做一次SPFA，求出他們兩個到每個城市的最短時間。
然后枚舉每個城市，求出在每個城市相遇所需的最短時間。
最后再把這些最短時間再求一次其中的最短時間，那個，就是答案了。

代碼

#include<cstdio> #include<iostream> #include<cmath> #include<queue> #include<cstring> using namespace std; struct note//定義結構體 {int x,next; }e[10001]; int n,m,ls[5001],x[5001],y[5001],s,t,k,a[5001][5001],an[5001],an1[5001],minn; bool in[5001]; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d%d",&s,&t);//讀入scanf("%d",&a[s][t]);//讀入a[t][s]=a[s][t];//因為是無向圖，所以來往兩邊都要賦長度e[++k]=(note){s,ls[t]};ls[t]=k;//建鄰接表e[++k]=(note){t,ls[s]};ls[s]=k;}scanf("%d%d",&s,&t);//讀入memset(an,117901064,sizeof(an));queue<int>l;//建隊列（SPFA）（以s為出發點）an[s]=0;l.push(s);while (!l.empty()){int hh=l.front();l.pop();for (int i=ls[hh];i;i=e[i].next)if (an[e[i].x]>an[hh]+a[hh][e[i].x]){an[e[i].x]=an[hh]+a[hh][e[i].x];if (!in[e[i].x]){l.push(e[i].x);in[e[i].x]=1;}}in[hh]=0;}int temp=s;s=t;t=temp;//再次SPFA（以t為出發點）memset(an1,117901064,sizeof(an));an1[s]=0;l.push(s);while (!l.empty()){int hh=l.front();l.pop();for (int i=ls[hh];i;i=e[i].next)if (an1[e[i].x]>an1[hh]+a[hh][e[i].x]){an1[e[i].x]=an1[hh]+a[hh][e[i].x];if (!in[e[i].x]){l.push(e[i].x);in[e[i].x]=1;}}in[hh]=0;}minn=117901064;//求相遇最短時間for (int i=1;i<=n;i++)if (i!=s&&i!=t) minn=min(minn,max(an[i],an1[i]));else if (i==s) minn=min(minn,an[i]);else minn=min(minn,an1[i]);if (minn!=117901064) printf("%d",minn);else printf("Peace!");return 0; }

總結

以上是生活随笔為你收集整理的腾讯大战360的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。