腾讯发布消息：存360则，不留QQ。留QQ，则须卸360。

　　 360则表示360与QQ可以共存。

　　 这也就标志着腾讯与360的大战就此开始！

描述 Description

  　　  现在，腾讯与360由于身处异地，非常迫切地想在最短的时间内相遇，然后干一架。但是由于双方的技术员都在努力地编程序想干掉对方，所以他们希望你来帮他们找到一个最好的方案使得相遇的时间最短。

　　   在此我们定义"相遇"为：两个人皆在同一个有编号的城市上就可以了，并且这两个人均可以站在原地等另外一个人。也就是说，在这里我们不考虑两人在路中间相遇。

输入格式 Input Format

  输入数据第一行：N和M（用空格隔开） 表示这是一个N个点的图并且有M条边

第二行到第M+1行 为这个图的详细信息。

　　  每行共有被空格隔开的三个数：a b c。表示编号为a的城市到编号为b的城市

　　  有一个双向边，并且要过这条双向边所需要花费的时间为c。

最后一行有两个数：S和T，S表示腾讯所处的城市（也就是深圳），T表示360所处的

城市（也就是北京）

输出格式 Output Format

  输出只有一行，D，表示二者"相遇"的最短时间。当然，如果无法相遇输出peace!

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #define oo 117901063
 6 using namespace std;
 7 int n,c,o=0;
 8 struct node
 9 {
10   int x,len,n;
11 }e[10010];
12 int k[10010];
13 int st,en;
14 int d[10010],f[1000000],tt[10010];
15 bool v[10010];
16 int ans;
17 void add(int x,int y,int z)
18 {
19     e[++o].x=y;
20     e[o].len=z;
21     e[o].n=k[x];
22     k[x]=o;
23 }
24 void spfa(int st,int en)
25 {
26   memset(d,63,sizeof(d));
27   memset(f,0,sizeof(f));
28   d[st]=0;
29   f[1]=st;
30   v[st]=true;
31   int head=1,tail=1,now;
32   while (head<=tail)
33   {
34       now=f[head];
35       v[now]=false;
36       int t=k[now];
37       while(t)
38       {
39           if (d[e[t].x]>d[now]+e[t].len) 
40           {
41             d[e[t].x]=d[now]+e[t].len;
42           if (!v[e[t].x])
43           {
44             v[e[t].x]=true;
45             f[++tail]=e[t].x;
46           }
47           }
48           t=e[t].n;
49       }
50       head++;
51   }
52 }
53 int main()
54 {
55   scanf("%d %d\n",&n,&c);
56   int a,b,q;
57   for (int i=1;i<=c;i++)
58   {
59      scanf("%d %d %d\n",&a,&b,&q);
60      add(a,b,q);
61      add(b,a,q);
62   }
63   scanf("%d %d\n",&st,&en);
64   spfa(st,en);
65   memcpy(tt,d,sizeof(d));
66   spfa(en,st);
67   ans=oo;
68   for (int i=1;i<=n;i++)
69   {
70       ans=min(ans,max(d[i],tt[i]));
71   }
72   if (ans<oo) printf("%d\n",ans);
73   else printf("Peace!\n");
74 //  system("pause");
75   return 0;
76 }
77 

I WILL BE BETTER 2010-11-09 18:46 发表评论