1. Dijkstra算法

适用范围：计算正权图上的单源最短路（Single-Source Shortest Paths,SSSP）。同时适用于有向图和无向图。

模板题：P4779 【模板】单源最短路径（标准版）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
const int INF=0x7fffffff;
struct Dijkstra{struct Edge{int from, to, dist;Edge(int u,int v,int d):from(u),to(v),dist(d) {}};struct HeapNode{int d,u;bool operator < (const HeapNode& rhs) const {return d > rhs.d;}};int n,m;vector<Edge> edges;vector<int> G[maxn];bool done[maxn];//是否已永久标记int d[maxn];//s到各个点的距离int p[maxn];//最短路中的上一条弧void init(int n){this->n=n;this->m=m;for(int i=0;i<n;i++) G[i].clear();edges.clear();} void AddEdge(int from,int to,int dist){edges.push_back(Edge(from,to,dist));m=edges.size();G[from].push_back(m-1);}void dijkstra(int s){priority_queue<HeapNode> Q;for(int i=1;i<=n;i++) d[i]=INF;d[s]=0;memset(done,0,sizeof(done));Q.push((HeapNode){0,s});while(!Q.empty()){HeapNode x=Q.top(); Q.pop();int u=x.u;if(done[u]) continue;done[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;p[e.to]=G[u][i];Q.push((HeapNode){d[e.to],e.to});}}}}
};
int n,m,s;
Dijkstra D;
void read_input(){int u,v,d;cin>>n>>m>>s;D.init(n);for(int i=0;i<m;i++){cin>>u>>v>>d;D.AddEdge(u,v,d);}
}
void solve(){D.dijkstra(s);for(int i=1;i<=n;i++) cout<<D.d[i]<<" ";cout<<"\n"; 
}
int main(){ios::sync_with_stdio(false);cin.tie(NULL); cin.tie(NULL);read_input();solve();return 0;
}

1.1 P7655 [BalticOI 1996 Day 2] A FAST JOURNEY（待补）

如果想要保证走的时间最短，就应该使用最短路，我们从一个点出发到一个点时，以天数为第一关键字，当前天数所剩时间为第二关键字进行优先队列的标准进行 Dij，如果当前天的时间加上走这条的时间小于等于 12 则可以转移，如果大于则无法转移。

但是这并不能覆盖样例的等候情况，因此我们需要判断是否能够在一个地点等一天，所以我们直接在判断之后进行一次下一天的过渡，在转移过程中记录相关信息，最后到终点时直接输出即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-f;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
struct node{int da,ti,np;friend bool operator < (node x,node y){if(x.da==y.da) return x.ti>y.ti;return x.da>y.da;}
};//天数，天数相同比较时间
priority_queue<node> q;
int hpla[110],st,to[2010],nxt[2010],head[2010],val[2010],fl[2010],cnt,vis[110][2][20],pre[110],hpt[110],hpti[110];
int ansp[110],ansx[110],anst[110],ansti[110];
void addedge(int x,int y,int z,int ff)
{to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;val[cnt]=z;fl[cnt]=ff;//正图还是反图
}
void out(int x,int &nc)
{
//	cout<<x<<nc<<endl;
//	if(x==0) return;ansp[nc]=pre[x];ansx[nc]=x;anst[nc]=hpt[x];ansti[nc]=hpti[x];//取出路径nc++;if(pre[x]==st) return;out(pre[x],nc);
}
int main()
{int x,y,z;st=read();int ed=read(),n=read(),m=read();memset(hpt,0x3f,sizeof(hpt));memset(hpti,0x3f,sizeof(hpti));for(int i=1;i<=m;i++){x=read(),y=read(),z=read();addedge(x,y,z,1);addedge(y,x,z,0);}vis[st][1][0]=1;q.push((node){1,0,st});while(!q.empty()){node nq=q.top();q.pop();
//		cout<<nq.np<<" "<<nq.da<<" "<<nq.ti<<endl;if(nq.np==ed)//到了直接输出{int cc=0;out(nq.np,cc);for(int i=cc-1;i>=0;i--){cout<<ansp[i]<<" "<<ansx[i]<<" "<<anst[i]<<" "<<ansti[i]<<endl;}return 0;}x=nq.np;int d=nq.da,tt=nq.ti;for(int i=head[x];i;i=nxt[i]){int ft=to[i],ro=val[i];if(tt+ro<=12)//如果一天还未结束{
//				cout<<ft<<" "<<ro<<endl;if(!vis[ft][d%2][tt+ro]&&d%2==fl[i])//当前时间没有走过{if(d<hpt[ft]||(d==hpt[ft]&&tt+ro<hpla[ft]))//剩余时间更优{pre[ft]=x;hpt[ft]=d;hpti[ft]=ro;hpla[ft]=ro+tt;}vis[ft][d%2][tt+ro]=1;q.push((node){d,tt+ro,ft});}}}if(!vis[x][(d+1)%2][0])//注意！可以选择在某个地方停留一天{q.push((node){d+1,0,x});}}
}