P1073-最优贸易

ゝ一世哀愁。 2023-06-01 08:57 11阅读 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 5053900
     8 typedef long long ll;
     9 
    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 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 int n,m;
    31 int v[maxn];
    32 typedef pair<int,int> P;
    33 int d[maxn];
    34 void shortest_path(int s)
    35 {
    36     priority_queue<P> que;
    37     memset(d,-0x3f,sizeof(d));
    38     d[s] = 0;
    39     que.push(P {
        0,s});
    40 
    41     while(!que.empty())
    42     {
    43         P p = que.top();
    44         que.pop();
    45         int v = p.second;
    46         if(d[v] > p.first) continue;
    47         for(int i = head[v]; i; i = Next[i])
    48         {
    49             int y = ver[i];
    50             int w = val[i];
    51             if(d[y] < d[v] + w)
    52             {
    53                 d[y] = d[v] + w;
    54                 que.push(P {d[y],y});
    55             }
    56         }
    57     }
    58 }
    59 int main()
    60 {
    61      n = read();
    62      m = read();
    63      _for(i,1,n+1)
    64          v[i] = read();
    65      _for(i,1,m+1)
    66      {
    67         int a = read();
    68         int b = read();
    69         int c = read(); 
    70         if(c==1)
    71         {
    72             add(a,b,0);
    73             add(n+a,n+b,0);
    74             add(2*n+a,2*n+b,0);
    75         }
    76         else
    77         {
    78             add(a,b,0);
    79             add(b,a,0);
    80             add(n+a,n+b,0);
    81             add(n+b,n+a,0);
    82             add(2*n+b,2*n+a,0);
    83             add(2*n+a,2*n+b,0);
    84         }    
    85     }
    86     _for(i,1,n+1)
    87      {
    88          add(i,i+n,-v[i]);
    89          add(i+n,i+n*2,v[i]);
    90     }
    91     shortest_path(1);
    92     printf("%d\n",max(0,d[3*n]));
    93     return 0;
    94 }

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