#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;
int val[100001],book[100001];
struct note {
int num=-99999;
int minn=99999;
} dis[100001];
vector <int > a[100001];
queue <int > q;
void add(int x,int y) {
a[x].push_back(y);
return ;
}
int main() {
cin>>n>>m;
int x,y,k;
for(int i=1; i<=n; i++) {
cin>>val[i];
}
for(int i=1; i<=m; i++) {
cin>>x>>y>>k;
if(k==1) {
add(x,y);
} else {
add(x,y);
add(y,x);
}
}
/*for(int i=1; i<=n; i++) {
for(int j=0; j<a[i].size(); j++) {
cout<<a[i][j]<<" ";
}
cout<<endl;
}*/
q.push(1);
dis[1].num=0;
book[1]=1;
for(int i=1; i<=n; i++) {
dis[i].minn=val[i];
}
while(!q.empty()) {
int t=q.front();
for(int k=0; k<a[t].size(); k++) {
int to=a[t][k];
if(dis[to].minn>dis[t].minn) {
dis[to].minn=dis[t].minn;
if(book[to]==0){
q.push(to);
book[to]=1;
}
}
if(dis[to].num<val[to]-dis[to].minn) {
dis[to].num=val[to]-dis[to].minn;
if(book[to]==0) {
q.push(to);
book[to]=1;
}
}
}
book[q.front()]=0;
q.pop();
}
int maxn=-99999;
for(int i=1; i<=n; i++) {
maxn=max(maxn,dis[i].num);
//cout<<dis[i].num<<" ";
}
//cout<<endl;
cout<<maxn;
return 0;
}
by danefishhh @ 2018-07-17 10:55:15
```cpp
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n,m;
int val[100001],book[100001];
struct note {
int num=-99999;//num表示到当前点的最大差值
int minn=99999;//minn表示到当前点路径上的val最小值
} dis[100001];
vector <int > a[100001];
queue <int > q;
void add(int x,int y) {
a[x].push_back(y);
return ;
}
int main() {
cin>>n>>m;
int x,y,k;
for(int i=1; i<=n; i++) {
cin>>val[i];
}
for(int i=1; i<=m; i++) {
cin>>x>>y>>k;
if(k==1) {
add(x,y);
} else {
add(x,y);
add(y,x);
}
}
/*for(int i=1; i<=n; i++) {
for(int j=0; j<a[i].size(); j++) {
cout<<a[i][j]<<" ";
}
cout<<endl;
}*/
q.push(1);
dis[1].num=0;
book[1]=1;
for(int i=1; i<=n; i++) {
dis[i].minn=val[i];
}
while(!q.empty()) {
int t=q.front();
for(int k=0; k<a[t].size(); k++) {
int to=a[t][k];
//更新最小值
if(dis[to].minn>dis[t].minn) {
dis[to].minn=dis[t].minn;
if(book[to]==0){
q.push(to);
book[to]=1;
}
}
//更新差值
if(dis[to].num<val[to]-dis[to].minn) {
dis[to].num=val[to]-dis[to].minn;
if(book[to]==0) {
q.push(to);
book[to]=1;
}
}
}
book[q.front()]=0;
q.pop();
}
int maxn=-99999;
for(int i=1; i<=n; i++) {
maxn=max(maxn,dis[i].num);
//cout<<dis[i].num<<" ";
}
//cout<<endl;
cout<<maxn;
return 0;
}
```
by danefishhh @ 2018-07-17 10:58:31
走到有的点就到不了终点了（同样WA）
by Zarinopl @ 2018-07-19 15:44:03