P1339-[USACO09OCT]热浪Heat Wave

骑猪看日落 2023-06-01 08:55 23阅读 0赞

1 #include <bits/stdc++.h>
     2 #define pb push_back
     3 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
     4 #define INF INT_MAX
     5 #define ll long long
     6 
     7 using namespace std;
     8 
     9 const int maxn = 500003;
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0');
    24 }
    25 struct edge
    26 {
    27     ll to;
    28     ll cost;
    29 };
    30 vector<edge> G[maxn];
    31 
    32 ll V,E;
    33 
    34 typedef pair<ll,ll> P;//first 是最短距离，second 是顶点编号 
    35 ll d[maxn];
    36 void shortest_path(ll s)
    37 {
    38     priority_queue<P,vector<P>,greater<P>> que;
    39     
    40     _for(i,1,V+1)
    41         d[i] = INF;
    42     d[s] = 0;
    43     que.push(P{
        0,s});
    44 
    45     while(!que.empty())
    46     {
    47         P p = que.top();que.pop();
    48         ll v = p.second;
    49         if(d[v] < p.first) continue;
    50         _for(i,0,G[v].size())
    51         {
    52             edge e = G[v][i];
    53             if(d[e.to] > d[v] + e.cost)
    54             {
    55                 d[e.to] = d[v] + e.cost;
    56                 que.push(P{d[e.to],e.to});
    57             }
    58         }
    59     }
    60 }
    61 
    62 int main()
    63 {
    64     ll st,ed;
    65     V = read(),E = read(),st = read(),ed = read();
    66 //    scanf("%d %d %d",&V,&E,&st);
    67     _for(i,0,E)
    68     {
    69         ll s,t,c;
    70         s = read(),t = read(),c = read();
    71         //  scanf("%d %d %d",&s,&t,&c);
    72         G[s].push_back(edge {t,c});
    73          G[t].push_back(edge{s,c});
    74     }
    75     shortest_path(st);
    76     write(d[ed]);
    77     //printf("%d ",d[i]);
    78     return 0;
    79 }

转载于:https://www.cnblogs.com/Asurudo/p/11516823.html