dijkstra 作用太局限了，只要当前点被标记那么就不再用它更新了，对呀这道题它不是求最短路的，而是求最小值和最大值的 所以祂可能被重复更新因此只能用spfa算法。
我解决了，变量更新错了。。
#include <bits/stdc++.h> using namespace std; const int MAXN = 100010,MAXM = 500000 +10; unordered_map<int,vector<int>> path; unordered_map<int,vector<int>> rpath; int price[MAXN]; int dp_max[MAXN],dp_min[MAXN]; int n,m; void spfa(int start_point,int type) { queue<int> q; unordered_set<int> inq; // printf("start_point:=%d\n",start_point); if(type >0) { dp_min[start_point] = price[start_point]; }else { dp_max[start_point] = price[start_point]; } q.push(start_point); inq.insert(start_point); while(q.size()) { int u = q.front();q.pop(); inq.erase(u); //cout << u<<endl; if(type>0) { //求最小值 for(int v: path[u]) { if(dp_min[v] > min(dp_min[u] ,price[v] ) ) { dp_min[v] = min(dp_min[u] ,price[v] ) ; // printf("v:=%d , %d\n",v,dp_min[v]); if(inq.count(v)==false) { inq.insert(v); q.push(v); } } } }else { for(int v: rpath[u]) { if(dp_max[v] < max(dp_max[u],price[v] ) ) { dp_max[v] = max(dp_max[u],price[v] ); // printf("r v:=%d , %d\n",v,dp_max[v]); if(inq.count(v)==false) { inq.insert(v); q.push(v); } } } } } } int main() { cin>> n>>m; for(int i=1;i<=n;++i) cin>> price[i]; // for(int i = 1; i <= n; i ++) // { // //cin >> value[i]; // dp_min[i] = 999999999; // dp_max[i] = -999999999;//先取一下极值，也就是初始化 // } memset(dp_min,0x3f,sizeof dp_min); memset(dp_max,-0x3f,sizeof dp_max); //path.clear(); //rpath.clear(); while (m -- ) { int a,b,c; cin>> a>>b>>c; // path[a].push_back(b); // rpath[b].push_back(a); // if(c == 2) { // path[b].push_back(a); // rpath[a].push_back(b); // } if(c==2) { path[a].push_back(b); path[b].push_back(a); rpath[a].push_back(b); rpath[b].push_back(a); }else { path[a].push_back(b); rpath[b].push_back(a); } } spfa(1,1); spfa(n,-1); int res = 0; for(int i=1;i<=n;++i) { // printf("dp_max[%d] = %d\n",i,dp_max[i]); // printf("dp_min[%d] = %d\n",i,dp_min[i]); res = max(res, dp_max[i] -dp_min[i]); } printf("%d\n",res); //cout << 0x3f<<endl; return 0; }
我这和题解是一模一样的算法啊，太难受了
## 大佬帮我看看这个写法 为什么过不了最后一个案例
#include <bits/stdc++.h> using namespace std; const int MAXN = 100010,MAXM = 500000 +10; unordered_map<int,vector<int>> path; unordered_map<int,vector<int>> rpath; int price[MAXN]; int dp_max[MAXN],dp_min[MAXN]; int n,m; void spfa(int start_point,int type) { queue<int> q; unordered_set<int> inq; printf("start_point:=%d\n",start_point); if(type >0) { dp_min[start_point] = price[start_point]; }else { dp_max[start_point] = price[start_point]; } q.push(start_point); inq.insert(start_point); while(q.size()) { int u = q.front();q.pop(); inq.erase(u); //cout << u<<endl; if(type>0) { //求最小值 for(int v: path[u]) { if(dp_min[v] > min(dp_min[u] ,price[u] ) ) { dp_min[v] = min(dp_min[u] ,price[u] ) ; printf("v:=%d , %d\n",v,dp_min[v]); if(inq.count(v)==false) { inq.insert(v); q.push(v); } } } }else { for(int v: rpath[u]) { if(dp_max[v] < max(dp_max[u],price[u] ) ) { dp_max[v] = max(dp_max[u],price[u] ); printf("r v:=%d , %d\n",v,dp_max[v]); if(inq.count(v)==false) { inq.insert(v); q.push(v); } } } } } } int main() { cin>> n>>m; for(int i=1;i<=n;++i) cin>> price[i]; // for(int i = 1; i <= n; i ++) // { // //cin >> value[i]; // dp_min[i] = 999999999; // dp_max[i] = -999999999;//先取一下极值，也就是初始化 // } memset(dp_min,0x3f,sizeof dp_min); memset(dp_max,-0x3f,sizeof dp_max); //path.clear(); //rpath.clear(); while (m -- ) { int a,b,c; cin>> a>>b>>c; // path[a].push_back(b); // rpath[b].push_back(a); // if(c == 2) { // path[b].push_back(a); // rpath[a].push_back(b); // } if(c==2) { path[a].push_back(b); path[b].push_back(a); rpath[a].push_back(b); rpath[b].push_back(a); }else { path[a].push_back(b); rpath[b].push_back(a); } } spfa(1,1); spfa(n,-1); int res = 0; for(int i=1;i<=n;++i) { printf("dp_max[%d] = %d\n",i,dp_max[i]); printf("dp_min[%d] = %d\n",i,dp_min[i]); res = max(res, dp_max[i] -dp_min[i]); } printf("%d\n",res); //cout << 0x3f<<endl; return 0; }
那这道题中的代码里 并没有判断图中是否有 负权回路啊，那么不就会一直更新吗，不理解。
当存在负权回路的时候才会一直更新，不存在的话求出最短路后就不再更新了，你看一下spfa中的更新代码
if(dist[j] > dist[t] + w[i])
只有瞒住上述条件才会更新，并且这道题也不是考察负环的，不存在负权回路。直接拿spfa做就行啦。
嗷嗷，也就是说这里这道题 不存在不权回路
对的
SPFA只是能多处理一个负边权罢了，dijikstra都可以
spfa能多次用一个边权变小的点去取更新它的子节点，而dijkstrar如果认定这个点是当前最小的那么就会被标记，即使下次这个点变小也不会用它去更新它的子节点，你不要只想到用它们做最普遍的最短路问题，其他类似的也能用，但要思考一下那种算法可以用。
有道理。。。
是么。。。
我解决了，变量更新错了。。
我这和题解是一模一样的算法啊，太难受了
## 大佬帮我看看这个写法 为什么过不了最后一个案例
那这道题中的代码里 并没有判断图中是否有 负权回路啊，那么不就会一直更新吗，不理解。
当存在负权回路的时候才会一直更新，不存在的话求出最短路后就不再更新了，你看一下spfa中的更新代码
只有瞒住上述条件才会更新，并且这道题也不是考察负环的，不存在负权回路。直接拿spfa做就行啦。
嗷嗷，也就是说这里这道题 不存在不权回路
对的
SPFA只是能多处理一个负边权罢了，dijikstra都可以
spfa能多次用一个边权变小的点去取更新它的子节点，而dijkstrar如果认定这个点是当前最小的那么就会被标记，即使下次这个点变小也不会用它去更新它的子节点，你不要只想到用它们做最普遍的最短路问题，其他类似的也能用，但要思考一下那种算法可以用。
有道理。。。
是么。。。