有关于最短路的题目。
我们先将将读入的原图存储下来，在存储一张原图的反向图，之后再进行一些操作。
我们在原图上求出一个数组d，其中d[i]表示从起点到i经过的点权最小的值，同理，我们在反向图上求出一个数组f，表示从终点到i经过的点权最大的值，这样一来，答案便是max(f[i]-d[i]).
我们在原图和反向图中各跑一遍迪杰斯特拉即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 inline int read() { 8 int ret=0; 9 int op=1; 10 char c=getchar(); 11 while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();} 12 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 13 return ret*op; 14 } 15 typedef pair<int,int> pii; 16 int n,m; 17 struct node { 18 int next,to; 19 }a1[500010<<1],a2[500010<<1]; 20 int head1[500010<<1],head2[500010<<1],num1,num2; 21 int val[100010]; 22 int f[100010],d[100010],ans,vis[100010]; 23 inline void add(int from,int to) { 24 a1[++num1].next=head1[from]; a1[num1].to=to; head1[from]=num1; 25 swap(from,to); 26 a2[++num2].next=head2[from]; a2[num2].to=to; head2[from]=num2; 27 } 28 int main() { 29 n=read(); m=read(); 30 for(int i=1;i<=n;i++) val[i]=read(); 31 for(int i=1;i<=m;i++) { 32 int x=read(),y=read(),z=read(); 33 if(z==1) { 34 add(x,y); 35 } 36 else { 37 add(x,y); 38 add(y,x); 39 } 40 } 41 memset(d,0x3f,sizeof(d)); 42 memset(vis,0,sizeof(vis)); 43 priority_queue<pii,vector<pii>,greater<pii> >q; 44 d[1]=val[1]; 45 q.push(make_pair(val[1],1)); 46 while(!q.empty()) { 47 int now=q.top().second; 48 q.pop(); 49 if(vis[now]) continue ; 50 vis[now]=1; 51 for(int i=head1[now];i;i=a1[i].next) { 52 int v=a1[i].to; 53 d[v]=min(d[now],val[v]); 54 q.push(make_pair(d[v],v)); 55 } 56 } 57 memset(f,0xcf,sizeof(f)); 58 memset(vis,0,sizeof(vis)); 59 while(!q.empty()) q.pop(); 60 f[n]=val[n]; 61 q.push(make_pair(val[n],n)); 62 while(!q.empty()) { 63 int now=q.top().second; 64 q.pop(); 65 if(vis[now]) continue ; 66 vis[now]=1; 67 for(int i=head2[now];i;i=a2[i].next) { 68 int v=a2[i].to; 69 f[v]=max(f[now],val[v]); 70 q.push(make_pair(f[v],v)); 71 } 72 } 73 ans=-1; 74 for(int i=1;i<=n;i++) 75 ans=max(ans,f[i]-d[i]); 76 printf("%d ",ans); 77 return 0; 78 }