嘟嘟嘟

 

换句话说，就是寻找一条从1到n的路径，使路径上两点x, y（先经过x再经过y）使val[x] - val[y]最大。

还可以用dp的思想来做这道题：令dis1[x]表示1到x的所有路径中val最小的点，dis2[x]表示从t到x的所有路径中val最大的点，这样答案就是max(dis2[x] - dis1[x])。

用dijkstra就可以实现这个dp。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<cstdlib>
  7 #include<cctype>
  8 #include<vector>
  9 #include<stack>
 10 #include<queue>
 11 using namespace std;
 12 #define enter puts("") 
 13 #define space putchar(' ')
 14 #define Mem(a) memset(a, 0, sizeof(a))
 15 typedef long long ll;
 16 typedef double db;
 17 const int INF = 0x3f3f3f3f;
 18 const db eps = 1e-8;
 19 const int maxn = 1e5 + 5;
 20 inline ll read()
 21 {
 22     ll ans = 0;
 23     char ch = getchar(), last = ' ';
 24     while(!isdigit(ch)) {last = ch; ch = getchar();}
 25     while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
 26     if(last == '-') ans = -ans;
 27     return ans;
 28 }
 29 inline void write(ll x)
 30 {
 31     if(x < 0) x = -x, putchar('-');
 32     if(x >= 10) write(x / 10);
 33     putchar(x % 10 + '0');
 34 }
 35 
 36 int n, m, a[maxn];
 37 vector<int> v[maxn], v2[maxn];
 38 
 39 #define pr pair<int, int>
 40 #define mp make_pair
 41 int dis1[maxn];
 42 bool in[maxn];
 43 void dij1(int s)
 44 {
 45     for(int i = 1; i <= n; ++i) dis1[i] = INF;
 46     dis1[s] = a[s];
 47     priority_queue<pr, vector<pr>, greater<pr> > q; q.push(mp(dis1[s], s));
 48     while(!q.empty())
 49     {
 50         int now = q.top().second; q.pop();
 51         if(in[now]) continue;
 52         in[now] = 1;
 53         for(int i = 0; i < (int)v[now].size(); ++i)
 54         {
 55             if(dis1[v[now][i]] > min(dis1[now], a[v[now][i]]))
 56             {
 57                 dis1[v[now][i]] = min(dis1[now], a[v[now][i]]);
 58                 q.push(mp(dis1[v[now][i]], v[now][i]));    
 59             }
 60         }
 61     }
 62 }
 63 
 64 int dis2[maxn];
 65 void dij2(int s)
 66 {
 67     Mem(in);
 68     dis2[s] = a[s];
 69     priority_queue<pr> q; q.push(mp(dis1[s], s));
 70     while(!q.empty())
 71     {
 72         int now = q.top().second; q.pop();
 73         if(in[now]) continue;
 74         in[now] = 1;
 75         for(int i = 0; i < (int)v2[now].size(); ++i)
 76         {
 77             if(dis2[v2[now][i]] < max(dis2[now], a[v2[now][i]]))
 78             {
 79                 dis2[v2[now][i]] = max(dis2[now], a[v2[now][i]]);
 80                 q.push(mp(dis2[v2[now][i]], v2[now][i]));    
 81             }
 82         }
 83     }
 84 }
 85 
 86 int ans = 0;
 87 
 88 int main()
 89 {
 90     n = read(); m = read();
 91     for(int i = 1; i <= n; ++i) a[i] = read();
 92     for(int i = 1; i <= m; ++i)
 93     {
 94         int x = read(), y = read(), z = read();
 95         v[x].push_back(y); v2[y].push_back(x); 
 96         if(z == 2) v[y].push_back(x), v2[x].push_back(y);
 97     }
 98     dij1(1);
 99     dij2(n);
100     for(int i = 1; i <= n; ++i) ans = max(ans, dis2[i] - dis1[i]);
101     write(ans); enter;
102     return 0;
103 }

View Code