国国の国王 @ 2022-11-15 18:04:42
#include<bits/stdc++.h>
using namespace std;
const int Maxm=2e5+5,Maxn=1e5+5;
struct Edge{
int u,v,w;
int next;
}e[Maxm];
int top;
struct Dist{
int v,w;//到V的距离是W
}pile[Maxm+Maxn];
int pt;//ptop
int head[Maxn];
int dis[Maxn];
bool vis[Maxn];
int n,m;
void reset(){
for(int i=1;i<=n;i++) dis[i]=2e9;
}
void Add(int u,int v,int w){
top++;
e[top].u=u;
e[top].v=v;
e[top].w=w;
e[top].next=head[u];
head[u]=top;
return;
}
void Put(int v,int w){
pile[++pt].v=v;
pile[pt].w=w;
int np=pt,fa=np/2;
while(fa){
if(pile[np].w>pile[fa].w) return;
swap(pile[np],pile[fa]);
np=fa;
fa=np>>1;
}
return;
}
void Pop(){
swap(pile[1],pile[pt]);
pt--;
int np=1,son=2;
while(son<=pt){
if(son<pt&&pile[son+1].w<pile[son].w) son++;
if(pile[son].w<pile[np].w) return;
swap(pile[np],pile[son]);
np=son;
son=np<<1;
}
return;
}
void Dijistra(int np){
Put(np,0);
while(pt){
int v=pile[1].v,w=pile[1].w;
Pop();
if(vis[v]) continue;
dis[v]=w;
vis[v]=1;
for(int i=head[v];i;i=e[i].next){
if(vis[e[i].v]) continue;
Put(e[i].v,w+e[i].w);
}
}
return;
}
int main(){
int u,v,w,s;
scanf("%d%d%d",&n,&m,&s);
reset();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
Add(u,v,w);
}
Dijistra(s);
for(int i=1;i<=n;i++) printf("%d ",dis[i]);
}
by yummy @ 2022-11-15 18:54:22
《Dijkstra 的 100 种拼法》
by 国国の国王 @ 2022-11-16 15:57:18
改正一下,题目是A一个点
by 国国の国王 @ 2022-11-16 16:15:32
@国国の国王
if(pile[son].w<pile[np].w) return;
已过,此贴终结