洛谷P1339 [USACO09OCT]热浪Heat Wave

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<queue>
 5 using namespace std;
 6 
 7 struct node{
 8     int value;
 9     int to;
10     node *next;
11 };
12 
13 const int maxn=10000;
14 int t,c,ts,te;
15 int dist[maxn];
16 int re,rs,ci;
17 node* line[maxn];
18 queue<int> q;
19 
20 void spfa(int src){
21     node *tmp;
22     int now;
23     q.push(src);
24     dist[src]=0;
25     while (!q.empty()){
26         now=q.front();
27         q.pop();
28         tmp=line[now]->next;
29         while (tmp){
30             if (dist[tmp->to]>dist[now]+tmp->value){
31                 dist[tmp->to]=dist[now]+tmp->value;
32                 q.push(tmp->to);
33             }
34             tmp=tmp->next;
35         }
36     }
37 }
38 
39 int main(){
40     //freopen("heatwave.in","r",stdin);
41     //freopen("heatwave.out","w",stdout);
42     scanf("%d%d%d%d",&t,&c,&ts,&te);
43     node *tmp;
44     for (int i=1;i<=t;++i){
45         dist[i]=maxn;
46         line[i]=new node;
47         line[i]->next=NULL;
48     }
49     for (int i=1;i<=c;++i){
50         tmp=new node;
51         scanf("%d%d%d",&rs,&re,&ci);
52         
53         tmp->to=re;
54         tmp->value=ci;
55         tmp->next=line[rs]->next; 
56         line[rs]->next=tmp;
57         
58         
59         tmp=new node;
60         tmp->to=rs;
61         tmp->value=ci;
62         tmp->next=line[re]->next;
63         line[re]->next=tmp;
64     }
65     
66     spfa(ts);
67     
68     cout<<dist[te];
69     //fclose(stdin);
70     //fclose(stdout);
71     return 0;
72 }