呃最短路要最好需要掌握的三种算法：dijkstra、SPFA、floyd；
区别在于：
·dijkstra最好用于稠密图；
·SPFA最好用于稀疏图；
·floyd可以用来写闭包（huaji）
·其他区别因为太菜暂时不列出来
先上个spfa模板：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<set> using namespace std; #define REG register #define REP(i,x,y) for(register int i=x;i<=y;i++) #define UP(i,x,y) for(register int i=x;i>=y;i--) #define IN inline #define inf 0x3f3f3f3f const int maxn=2505,maxm=6205; int dis[maxn]={0},head[maxm*2]={0},tot=0,n,m,ts,te; bool vis[maxn]={0}; struct edge{ int next,to,w; }h[maxm*2]; queue <int> Q; IN void add(int u,int v,int w){ h[++tot].next=head[u],h[tot].to=v,h[tot].w=w,head[u]=tot; } IN void SPFA(){ REP(i,1,n) dis[i]=inf; int u,v; Q.push(ts); dis[ts]=0;vis[ts]=1; while(!Q.empty()){ int u=Q.front();Q.pop(); vis[u]=0; for(REG int i=head[u];i;i=h[i].next){ v=h[i].to; if(dis[v]>dis[u]+h[i].w){ dis[v]=dis[u]+h[i].w; if(!vis[v]){ vis[v]=1;Q.push(v); } } } } } int main(){ scanf("%d %d %d %d",&n,&m,&ts,&te); REP(i,1,m){ int x,y,z; scanf("%d %d %d",&x,&y,&z); add(x,y,z);add(y,x,z); } SPFA(); printf("%d",dis[te]); return 0; }
·负环：进队次数>n就有负环；或开数组记录步数(最短路路径条数)，步数>n即有负环。
IN void spfa(int s){ if(flag) return; vis[s]=1; for(int i=head[s];i;i=e[i].ne){ if(flag) return; int to=e[i].to; if(d[to]>d[s]+e[i].va){ d[to]=d[s]+e[i].va; if(vis[to]){flag=1;return;} else spfa(to); } } vis[s]=0; }
再来个dijkstra模板（堆优化）：
（因现在水平真心菜，等更好理解重新不丑的）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<set> using namespace std; #define REG register #define REP(i,x,y) for(register int i=x;i<=y;i++) #define UP(i,x,y) for(register int i=x;i>=y;i--) #define IN inline #define inf 0x7fffffff struct node { int to,dis; bool operator <(const node &t) const { return dis>t.dis; } }; int n,m,s; bool visit[10050]; int dis[500050]; vector <node> g[10050]; priority_queue <node> q; int main() { scanf("%d%d%d",&n,&m,&s); for (int i=1;i<=m;i++) dis[i]=inf; for (int i=1;i<=m;i++) { int u,v,d; scanf("%d%d%d",&u,&v,&d); g[u].push_back((node){v,d}); } dis[s]=0; q.push((node){s,0}); while (!q.empty()) { node p=q.top(); q.pop(); int x=p.to; if (visit[x]) continue; visit[x]=1; for (int i=0;i<g[x].size();i++) { node np=g[x][i]; int x1=np.to; if (dis[x1]>dis[x]+np.dis) { dis[x1]=dis[x]+np.dis; q.push((node){x1,dis[x1]}); } } } for (int i=1;i<=n;i++) printf("%d ",dis[i]); printf(" "); return 0; }
然后就是floyd，这个真心不会，只能来个裸的三循环：
REP(k,1,n) REP(i,1,n) REP(j,1,n) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
接着来个差分约束系统：
先来个 两边夹定理：A-B=C <=> A-B>=C&&A-B<=C，
还有著名的三角形不等式；
应用：
1、线性约束：
对于所有满足d[x] - d[y] <= z的不等式，从y向x建立一条权值为z的有向边。
然后从起点1出发，利用SPFA求到各个点的最短路，如果1到N不可达，说明最短路(即上文中的T)无限长，输出-2。如果某个点进入队列大于等于N次，则必定存在一条负环，即没有最短路，输出-1。否则T就等于1到N的最短路。
2、区间约束；
3、未知条件约束：指在不等式的右边不一定是个常数，可能是个未知数，可以通过枚举这个未知数，然后对不等式转化成差分约束进行求解
注意;
1、可以开二维来进行其它的判断（例如 颜色不同的路才能走）
（待完善）