腾讯发布消息:存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
posted on 2010-11-09 18:46
I WILL BE BETTER 阅读(245)
评论(0) 编辑 收藏 引用