P2939-[USACO09FEB]改造路Revamping Trails

矫情吗；* 2023-06-01 08:57 55阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     4 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     5 #define INF 0x3f3f3f3f
     6 #define pb push_back
     7 #define maxn 5000039
     8 typedef long long ll;
     9 inline ll read()
    10 {
    11     ll ans = 0;
    12     char ch = getchar(), last = ' ';
    13     while(!isdigit(ch)) last = ch, ch = getchar();
    14     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    15     if(last == '-') ans = -ans;
    16     return ans;
    17 }
    18 inline void write(ll x)
    19 {
    20     if(x < 0) x = -x, putchar('-');
    21     if(x >= 10) write(x / 10);
    22     putchar(x % 10 + '0');
    23 }
    24 int n,m,k;
    25 int tot,ver[maxn],Next[maxn],head[maxn],val[maxn];
    26 void add(int x,int y,int t)
    27 {
    28     ver[++tot] = y,Next[tot] = head[x],head[x] = tot,val[tot] = t;
    29 }
    30 typedef pair<int,int> P;
    31 int d[maxn];
    32 void shortest_path(int s)
    33 {
    34     priority_queue<P,vector<P>,greater<P>> que;
    35     memset(d,0x3f,sizeof(d));
    36     d[s] = 0;
    37     que.push(P{
        0,s});
    38 
    39     while(!que.empty())
    40     {
    41         P p = que.top();que.pop();
    42         int v = p.second;
    43         if(d[v] < p.first) continue;
    44         for(int i = head[v]; i; i = Next[i])
    45         {
    46           //  cout << i << endl;
    47             int y = ver[i];
    48             int w = val[i];
    49             if(d[y] > d[v] + w)
    50             {
    51                 d[y] = d[v] + w;
    52                 que.push(P{d[y],y});
    53             }
    54         }
    55     }
    56 }
    57 int main()
    58 {
    59     n = read(), m = read(), k = read();
    60     _for(i,1,m+1)
    61     {
    62         int u,v,t;
    63         u = read();v = read();t = read();
    64         add(u,v,t),add(v,u,t);
    65         _for(j,1,k+1)
    66         {
    67             add(j*n+u,j*n+v,t),add(j*n+v,j*n+u,t);
    68             add((j-1)*n+u,j*n+v,0),add((j-1)*n+v,j*n+u,0);
    69         }
    70     }
    71     shortest_path(1);
    72     int ans = d[n];
    73     _for(i,1,k+1)
    74         ans = min(ans,d[i*n+n]);
    75     write(ans);
    76     return 0;
    77 }

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