P1339 [USACO09OCT]热浪Heat Wave（SPFA）

--------------------------------------

农夫约翰再显神威，双向热浪，双倍数组

（双倍大小，否则RE）

----------------------------------

题目链接：MIKU

-----------------------------------

怎么说呢，裸的最短路，但是好像floyd不优化不行

SPFA好写是好写，但是容易被卡

有空还是学Dijkstra比较好

-----------------------------------

SPFA我觉得就是贪心，从初始点开始一圈一圈的往外扩，然后找的（或者被卡），竞赛最好不要用

--------------------------------

 1 /*
 2 这题，双向边，双向数组，呃呃呃
 3 
 4 我竟然没发觉 
 5 
 6 */
 7 
 8 
 9 #include<iostream>
10 #include<cstdio>
11 #include<queue>
12 #include<cstring>
13 using namespace std;
14 
15 int t,c,ts,te;
16 queue<int> q;
17 int x,y,z;
18 int head[500010];
19 int n;
20 long long int dis[500010];
21 int vis[500010];
22 struct b{
23 int next;
24 
25 int to;
26 
27 long long int v;
28 } bian[500010];
29 //邻接链表存边 
30 void l(int f,int t,int va){
31     n++;
32     bian[n].next=head[f];
33     bian[n].to=t;
34     bian[n].v=va;
35     head[f]=n;
36 }
37 
38 int main(){
39     cin>>t>>c>>ts>>te;
40     memset(dis,0x3f,sizeof(dis));//初始化 
41     for(int i=1;i<= c;++i){
42         cin>>x>>y>>z;
43         l(x,y,z);
44         l(y,x,z);//双向存边 
45     }
46     vis[ts]=1;//记录入队 
47     dis[ts]=0;//初始化距离 
48     q.push(ts);//入队 
49     do{
50         int u=q.front();//spfa 
51         q.pop();
52         vis[u]=0;
53         for(int i=head[u];i;i=bian[i].next){//关键 
54             int v=bian[i].to;
55             if(dis[v]>dis[u]+bian[i].v){
56             dis[v]=dis[u]+bian[i].v;
57             if(!vis[v])
58             {
59                 vis[v]=1;
60                 q.push(v);
61             }
62         }
63         }
64     }while(!q.empty());
65     cout<<dis[te];
66     return 0;
67 }

------------------

（听说拜MIKU可以A题哦）

（喝水也能）