本文共 3944 字，大约阅读时间需要 13 分钟。

编号从1开始

dijkstra(正权)

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<bitset>#include<cassert>#include<cctype>#include<cmath>#include<cstdlib>#include<ctime>#include<deque>#include<iomanip>#include<list>#include<map>#include<queue>#include<set>#include<stack>#include<vector>#include<unordered_set>#include<unordered_map>using namespace std;//extern "C"{void *__dso_handle=0;}typedef long long ll;typedef long double ld;#define fi first#define se second#define pb push_back#define mp make_pair#define pii pair<int,int>#define lowbit(x) x&-xconst double PI=acos(-1.0);const double eps=1e-6;const ll mod=1e9+7;const int inf=0x3f3f3f;const int maxn=1e5+10;const int maxm=100+10;#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);struct Edge{   	int from,to,dist;	Edge(int u,int v,int d):from(u),to(v),dist(d){    }};int n,m;vector<Edge> edges;vector<int> G[maxn];bool vis[maxn];int d[maxn];int f[maxn];void init(int n){   	for(int i=0;i<=n;i++) G[i].clear();	edges.clear();}void addEdge(int u,int v,int d){   	edges.push_back(Edge(u,v,d));	G[u].push_back(edges.size()-1);}void dijkstra(int s){   	priority_queue<pii,vector<pii>,greater<pii> > que;	while(!que.empty()) que.pop();	for(int i=1;i<=n;i++) d[i]=inf;	d[s]=0;	memset(vis,0,sizeof(vis));	que.push(mp(0,s));	while(!que.empty())	{   		pii tmp=que.top(); que.pop();		int u=tmp.second;		if(vis[u]) continue;		vis[u]=true;		for(int i=0;i<G[u].size();i++)		{   			Edge e=edges[G[u][i]];			if(d[e.to]>d[u]+e.dist)			{   				d[e.to]=d[u]+e.dist;				f[e.to]=G[u][i];				que.push(mp(d[e.to],e.to));			}		}	}}int main(){   	init(n);	scanf("%d%d",&n,&m);	for(int i=0;i<m;i++){   		int u,v,d;		scanf("%d%d%d",&u,&v,&d);		addEdge(u,v,d);	}	for(int j=1;j<=n;j++)	{   		dijkstra(j);		for(int i=1;i<=n;i++) cout << d[i] << ' ';		cout << endl;	}}//4 8//1 2 2//1 3 6//1 4 4//2 3 3//3 1 7//3 4 1//4 1 5//4 3 12//0 2 5 4 //9 0 3 4 //6 8 0 1 //5 7 10 0 

SPFA(负权)

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<bitset>#include<cassert>#include<cctype>#include<cmath>#include<cstdlib>#include<ctime>#include<deque>#include<iomanip>#include<list>#include<map>#include<queue>#include<set>#include<stack>#include<vector>#include<unordered_set>#include<unordered_map>using namespace std;//extern "C"{void *__dso_handle=0;}typedef long long ll;typedef long double ld;#define fi first#define se second#define pb push_back#define mp make_pair#define pii pair<int,int>#define lowbit(x) x&-xconst double PI=acos(-1.0);const double eps=1e-6;const ll mod=1e9+7;const int inf=0x3f3f3f3f;const int maxn=2e5+10;const int maxm=100+10;#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);struct Edge{   	int from,to,dist;	Edge(int u,int v,int d):from(u),to(v),dist(d){   }};int n,m;vector<Edge> edges;vector<int> G[maxn];bool inq[maxn];int d[maxn],cnt[maxn],f[maxn];void init(){   	for(int i=0;i<=n;i++) G[i].clear();	edges.clear();}void addEdge(int u,int v,int d){   	edges.push_back(Edge(u,v,d));	G[u].push_back(edges.size()-1);}bool spfa(int s){   	memset(inq, 0, sizeof(inq));	memset(cnt, 0, sizeof(cnt));	for(int i=0;i<=n;i++) d[i]=inf;	queue<int> que;	while(!que.empty()) que.pop();	d[s]=0;	inq[s]=true;	que.push(s);	while(!que.empty())	{   		int u=que.front();que.pop();		inq[u]=false;		for(int i=0;i<G[u].size();i++)		{   			Edge e=edges[G[u][i]];			if(d[u]<inf && d[e.to]>d[u]+e.dist)			{   				d[e.to]=d[u]+e.dist;				f[e.to]=G[u][i];				if(!inq[e.to])				{   					que.push(e.to);					inq[e.to]=true;					if(++cnt[e.to]>=n) return false;				}			}		}	}	return true;}int main(){   	init();	scanf("%d%d",&n,&m);	for(int i=0;i<m;i++){   		int u,v,d;		scanf("%d%d%d",&u,&v,&d);		addEdge(u,v,d);	}	for(int j=1;j<=n;j++)	{   		if(!spfa(j)) {    cout << "FUCK!!" << endl; continue; }		for(int i=1;i<=n;i++) printf("%d ",d[i]);		printf("\n");	}}//4 8//1 2 2//1 3 6//1 4 4//2 3 3//3 1 7//3 4 1//4 1 5//4 3 12//0 2 5 4//9 0 3 4 //6 8 0 1 //5 7 10 0