这是图。
by Jean_Georges @ 2018-09-18 15:54:23
貌似你的数据多了数吧？
by B1GGersnow @ 2018-09-27 19:42:43
我的跑出来是8，代码比较垃圾。。
```cpp
#include<cstdio>
#include<queue>
#include<vector>
#include<map>
#include<cstring>
#include<algorithm>
#define MAXN 100005
using namespace std;
int d[MAXN],f1[MAXN],f2[MAXN],vis[MAXN],n,m,x,y,z,to,ans;
vector<int> p1[MAXN],p2[MAXN];
char c;
int read(){
c = getchar();
while(c < '0' || '9' < c)
c = getchar();
int x = 0;
while('0' <= c && c <= '9'){
x = 10 * x + c - '0';
c = getchar();
}
return x;
}
struct Node{
int d,u;
bool operator < (const Node & rhs)const{
return d > rhs.d;
}
};
struct Nodet{
int d,u;
bool operator < (const Nodet & rhs)const{
return d < rhs.d;
}
};
int main(){
//freopen("testdata.in","r",stdin);
n = read();m = read();
for(int i = 1;i <= n;i++)
d[i] = read();
for(int i = 1;i <= m;i++){
x = read();y = read();z = read();
if(z == 1){
p1[x].push_back(y);
p2[y].push_back(x);
}else{
p1[x].push_back(y);
p1[y].push_back(x);
p2[x].push_back(y);
p2[y].push_back(x);
}
}
memset(f1,0x3f,sizeof(f1));
f1[1] = d[1];
priority_queue<Node> q;
q.push((Node){f1[1],1});
while(!q.empty()){
Node s = q.top(); q.pop();
x = s.u;
if(vis[x])
continue;
vis[x] = 1;
for(int i = 0;i < p1[x].size();i++){
to = p1[x][i];
if(min(f1[x],d[to]) < f1[to]){
f1[to] = min(f1[x],d[to]);
q.push((Node){f1[to],to});
}
}
}
memset(vis,0,sizeof(vis));
memset(f2,~0x3f,sizeof(f2));
f2[n] = d[n];
priority_queue<Nodet> q2;
q2.push((Nodet){f2[n],n});
while(!q2.empty()){
Nodet s = q2.top(); q2.pop();
x = s.u;
if(vis[x])
continue;
vis[x] = 1;
for(int i = 0;i < p2[x].size();i++){
to = p2[x][i];
if(max(f2[x],d[to]) > f2[to]){
f2[to] = max(f2[x],d[to]);
q2.push((Nodet){f2[to],to});
}
}
}
for(int i = 1;i <= n;i++){
ans = max(ans,f2[i] - f1[i]);
//printf("%d %d\n",f1[i],f2[i]);
}
printf("%d\n",ans);
return 0;
}
```
你的数据应该是
```
8 9
5 5 2 5 5 10 5 5
1 2 1
2 8 1
2 4 1
4 5 1
5 6 1
6 2 1
2 7 1
7 3 1
3 2 1
```
但是你构造的数据多了一个数，就是line2有9个数
```
8 9
5 5 2 5 5 10 5 5 5
1 2 1
2 8 1
2 4 1
4 5 1
5 6 1
6 2 1
2 7 1
7 3 1
3 2 1
```
by B1GGersnow @ 2018-09-27 21:19:27