TOJ--2674--最短路(spfa)

厌死了......排位晋级赛两连跪。。。

三角形的那题还是无限WA 。。。

还有明天又要早起。。。

先还是来看下这题吧话说好久没写最短路了 --------- spfa 是我最喜欢的最短路版本

　　　　　　touch me

这题其实相比其它的最短路还是有个很让人看不懂的地方---让我纠结了很久

首先它告诉了我们城市的编号是从 1~1000

然后又突然告诉我们哪些城市和我们的出发地相邻假如是 1 10 100.。。之类的

最后告诉我们你想取哪些城市

我就在想起点呢！！！你肯定是通过相邻的城市扩散出去..然后不断稀疏操作,,,,

打完把LOL 我想到下标0 TM的还没有用过它。。。

题目给点提示不可以吗作妹啊

这题我本来是想用邻接表写的但是因为这里2条路之间可能存在多条道路所以要不断更新最短距离所以我就用map 二维数组来写了主要是嫌太烦了在输入的时候得遍历一下起点或终点相邻边找下有没有对应的点我觉得这样每次一个for 好烦的。。。

虽然 map二维数组真的很浪费空间时间但这里为了简便

其实最开始我是用floyd 可能因为结点数1000太多了吧对于O（n^3) 而言 TLE了或者我写差了。。

你用floyd AC了麻烦下面给我留言让我看下 thanks

关于 spfa 网上有很多介绍而且 spfa 不难理解只是不断的从队列中取出一个结点不断尝试地与它相邻结点进行稀疏操作仅此而已

啰嗦了一大堆贴代码了

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int inf = 0x3f3f3f3f;
 8 const int size = 1010;
 9 
10 int map[size][size];
11 int dist[size];
12 int go[size];
13 bool vis[size];
14 
15 void spfa()
16 {
17     int i , now;
18     memset(vis, false, sizeof(vis));
19     for(i = 0; i < size; i++) 
20         dist[i] = (i==0)?0:inf;
21     queue<int>qe;
22     while( !qe.empty() )
23         qe.pop();
24     qe.push(0);
25     vis[0] = true;
26     while(!qe.empty())
27     {
28         now = qe.front();
29         for(i = 0; i < size; i++)
30         {
31             if(dist[i] > dist[now] + map[now][i])
32             {
33                 dist[i] = dist[now] + map[now][i];
34                 if( !vis[i] )
35                 {
36                     qe.push(i);
37                     vis[i] = true;
38                 }
39             }
40         }    
41         qe.pop();
42         vis[now] = false;
43     }
44 }
45 
46 int main()
47 {
48     int t , s ,d;
49     int i , j , mmin;
50     int next, st, end, len;
51     while( ~scanf("%d %d %d", &t, &s, &d) )
52     {
53         for(i = 0; i < size; i++)
54             for(j = 0; j <=i; j++)
55                 if(i == j)
56                     map[i][j] = 0;
57                 else
58                     map[i][j] = map[j][i] = inf;
59         while(t--)
60         {
61             scanf("%d %d %d", &st, &end, &len); 
62             if( len < map[st][end] )
63                 map[st][end] = map[end][st] = len;
64         }
65         for(i = 0; i < s; i++)  
66         {
67             scanf("%d", &next);
68             map[0][next] = map[next][0] = 0;
69         }
70         for(i = 0; i < d; i++)  
71             scanf( "%d",&go[i] );
72         spfa();
73         mmin = inf;
74         for(i = 0; i < d; i++)  
75         {
76             if( dist[ go[i] ] < mmin )
77                 mmin = dist[ go[i]  ];
78         }
79         printf("%d
", mmin);
80     }
81     return 0;
82 }

View Code

又已经是次日凌晨了~~

just follow your heart