Dijkstra+优先队列
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
struct Dijkstra {
int n,m,first[maxn],next[maxm],done[maxn],d[maxn];
struct Edge {int from,to,dist;}edges[maxm];
struct HeapNode {
int d,u;
bool operator < (const HeapNode& ths) const {return d>ths.d;}
};
void init(int n) {
this->n=n;m=;
memset(first,,sizeof(first));
}
void AddEdge(int u,int v,int w) {
edges[++m]=(Edge){u,v,w};next[m]=first[u];first[u]=m;
}
void solve(int s) {
priority_queue<HeapNode> Q;
memset(done,,sizeof(done));
for(int i=;i<=n;i++) d[i]=;
d[s]=;Q.push((HeapNode){,s});
while(!Q.empty()) {
int x=Q.top().u;Q.pop();
if(done[x]) continue;done[x]=;
for(int i=first[x];i;i=next[i]) {
Edge& e=edges[i];
if(d[e.to]>d[x]+e.dist) {
d[e.to]=d[x]+e.dist;
Q.push((HeapNode){d[e.to],e.to});
}
}
}
}
}sol;
int main() {
int n=read(),m=read();sol.init(n);
for(int i=;i<=m;i++) {
int u=read(),v=read(),w=read();
sol.AddEdge(u,v,w);
}
sol.solve();
for(int i=;i<=n;i++) printf("%d ",sol.d[i]);
return ;
}
/*
7 8
1 3 5
1 4 2
1 5 1
4 3 2
3 6 2
4 6 3
6 7 3
5 7 1
*/
SPFA
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
struct SPFA {
int n,m,first[maxn],next[maxm],inq[maxn],d[maxn];
struct Edge {int from,to,dist;}edges[maxm];
void init(int n) {
this->n=n;m=;
memset(first,,sizeof(first));
memset(inq,,sizeof(inq));
}
void AddEdge(int u,int v,int w) {
edges[++m]=(Edge){u,v,w};next[m]=first[u];first[u]=m;
}
void solve(int S) {
queue<int> Q;Q.push(S);
for(int i=;i<=n;i++) d[i]=;d[S]=;
while(!Q.empty()) {
int u=Q.front();Q.pop();inq[u]=;
for(int i=first[u];i;i=next[i]) {
Edge& e=edges[i];
if(d[e.to]>d[u]+e.dist) {
d[e.to]=min(d[e.to],d[u]+e.dist);
if(!inq[e.to]) inq[e.to]=,Q.push(e.to);
}
}
}
}
}sol;
int main() {
int n=read(),m=read();sol.init(n);
for(int i=;i<=m;i++) {
int u=read(),v=read(),w=read();
sol.AddEdge(u,v,w);
}
sol.solve();
for(int i=;i<=n;i++) printf("%d ",sol.d[i]);
return ;
}
/*
7 8
1 3 5
1 4 2
1 5 1
4 3 2
3 6 2
4 6 3
6 7 3
5 7 1
*/
SPFA优化（还是有些用的）
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
struct SPFA {
int n,m,first[maxn],next[maxm],inq[maxn],d[maxn];
struct Edge {int from,to,dist;}edges[maxm];
void init(int n) {
this->n=n;m=;
memset(first,,sizeof(first));
memset(inq,,sizeof(inq));
}
void AddEdge(int u,int v,int w) {
edges[++m]=(Edge){u,v,w};next[m]=first[u];first[u]=m;
}
void solve(int S) {
deque<int> Q;Q.push_back(S);
for(int i=;i<=n;i++) d[i]=;d[S]=;
while(!Q.empty()) {
int u=Q.front();Q.pop_front();inq[u]=;
for(int i=first[u];i;i=next[i]) {
Edge& e=edges[i];
if(d[e.to]>d[u]+e.dist) {
d[e.to]=min(d[e.to],d[u]+e.dist);
if(!inq[e.to]) {
inq[e.to]=;
if(!Q.empty()&&d[e.to]<d[Q.front()]) Q.push_front(e.to);
else Q.push_back(e.to);
}
}
}
}
}
}sol;
int main() {
int n=read(),m=read();sol.init(n);
for(int i=;i<=m;i++) {
int u=read(),v=read(),w=read();
sol.AddEdge(u,v,w);
}
sol.solve();
for(int i=;i<=n;i++) printf("%d ",sol.d[i]);
return ;
}
/*
7 8
1 3 5
1 4 2
1 5 1
4 3 2
3 6 2
4 6 3
6 7 3
5 7 1
*/