最短路径
把处理的加入队列，下次也是从队列取出来处理，直到队列空了。感觉跟我第一次错迪杰斯特拉一样，但是这个好理解也简单。
漏了两个处理：1是记录已经在队列的就不要入了。2是记录进入队列次数，超过n就是负数。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>using namespace std;
int INF=0x3f3f3f3f;int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,m,a,b,c;cin >> n>> m;vector<vector<pair<int,int>>> ev(n+1);for (int i = 0; i < m; i ++ ){cin >> a >> b >> c;ev[a].push_back({b,c});}queue<int> Q;vector<int> dist(n+1,INF);dist[1] = 0;Q.push(1);int now,e,v;while(!Q.empty()){now = Q.front();Q.pop();for(auto x:ev[now]){e = x.first;v = x.second;if(dist[e]<=dist[now]+v){dist[e] = dist[e];}else{dist[e] = dist[now] + v;Q.push(e);}}}if(dist[n]>INF/2){cout << "impossible";}else{cout << dist[n];}return 0;
}判断负权回路
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,m,a,b,c;cin >> n >> m;int INF=0x3f3f3f3f;vector<int> dist(n+1,INF);vector<vector<pair<int,int>>> ev(n+1);vector<int> innum(n+1,1);//由于全部入队，都是1，记录入队次数，大于n就是有负权queue<int> Q;vector<bool> inflag(n+1,true);//都是1,记录入队情况for (int i = 0; i < m; i ++ ){cin >> a >> b >> c;ev[a].push_back({b,c});}for (int i = 1; i <= n; i ++ ){Q.push(i);//先全部入队}dist[1] = 0;while(!Q.empty()){int now = Q.front();Q.pop();inflag[now] = false;for(auto x: ev[now]){int e = x.first;int v = x.second;if(dist[e]>dist[now]+v){dist[e] = dist[now] + v;if(!inflag[now]){Q.push(e);innum[e]++;}if(innum[e]>n){cout << "Yes";return 0;}}}}cout << "No";
}