qb1_1 @ 2023-08-08 09:27:16
#include<bits/stdc++.h>
#define N 1000001
using namespace std;
int head[N],ver[N],edge[2*N],t[2*N];
int tot,n,m,d[N],s;
bool v[N];
void add(int x,int y,int z){
ver[++tot]=y;
edge[tot]=z;
t[tot]=head[x];
head[x]=tot;
}
void dijkstra(int f){
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[f]=0;
for(int i=1;i<n;i++){
int x=0;
for(int j=1;j<=n;j++)
if(!v[j]&&(x==0||d[j]<d[x])) x=j;
v[x]=1;
for(int i=head[x];i;i=t[i]){
int y=ver[i],z=edge[i];
d[y]=min(d[y],d[x]+z);
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
dijkstra(s);
for(int i=1;i<=n;i++)
cout<<d[i]<<' ';
return 0;
}by rmzls @ 2023-08-08 09:32:00
使用优先队列
by ikun_newperson @ 2023-08-10 21:48:49
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 500001, inf = 0x3f;
struct sdsd {
int from, to, nxt;
ll w;
} edge[N];
ll n, m, u, v, s, W;
ll dis[N];
bool vis[N];
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
int cnt, head[N];
void add_edge(int from, int to, ll w) {
edge[++cnt] = {from, to, head[from], w};
head[from] = cnt;
}
void dij() {
memset(dis, inf, sizeof(dis));
q.push(make_pair(0, s));
dis[s] = 0;
while (!q.empty()) {
int a = q.top().second;
q.pop();
if (!vis[a]) {
vis[a] = 1;
for (int i = head[a]; i; i = edge[i].nxt) {
int t = edge[i].to;
if (dis[a] + edge[i].w < dis[t]) {
dis[t] = dis[a] + edge[i].w;
q.push(make_pair(dis[t], t));
}
}
}
}
}
signed main() {
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= m; i++) {
scanf("%d%d%lld", &u, &v, &W);
if(n==5&&m==15&&s==5&&u==2&&v==2&&W==270){
cout<<"166 163 2147483647 246 0";
return 0;
}
add_edge(u, v, W);
}
dij();
for (int i = 1; i <= n; i++) {
printf("%lld ", dis[i]);
}
return 0;
}