shuman @ 2024-10-25 21:08:56
#include <bits/stdc++.h>
using namespace std;
int head[202000], cnt, n, m, s;
long long dis[202000];
bool vis[202000];
struct Edge
{
int to, dis;
int next;
}edge[202000];
struct dot
{
int id, dis;
bool operator < (const dot & x) const
{
return x.dis < dis;
}
};
void addline(int u, int v, int w)
{
cnt++;
edge[cnt].to = v;
edge[cnt].dis = w;
edge[cnt].next = head[u];
head[u] = cnt;
}
priority_queue<dot> q;
void dijistra()
{
while (!q.empty())
{
dot tmp = q.top();
int num = tmp.id;
q.pop();
if (vis[num]) continue;
else
{
vis[num] = 1;
for (int i = head[num]; i; i = edge[i].next)
{
int e = edge[i].to;
if (dis[e] > dis[num] + edge[i].dis)
{
dis[e] = dis[num] + edge[i].dis;
if (!vis[e])
{
q.push((dot){e, dis[e]});
}
}
}
}
}
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
addline(u, v, w);
}
for (int i = 1; i <= n; i++) dis[i] = 99999933;
dis[s] = 0;
q.push((dot){s, 0});
dijistra();
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}by __kd @ 2024-10-25 21:12:00
dis 初值小了吧
by zhanghaoyu1234567890 @ 2024-11-03 11:57:14
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PDD;
const int N=1000001;
int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N];
bool used[N];
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
void djstl(int s){
memset(dist,0x3f,sizeof(dist));
dist[s]=0;
priority_queue<PDD, vector<PDD>, greater<PDD> > heap;
heap.push({0,1});
while(heap.size()){
PDD t=heap.top();
heap.pop();
int u=t.second;
int dstnc=t.first;
if(used[u]) continue;
used[u]=true;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dstnc+w[i]){
dist[j]=dstnc+w[i];
heap.push({dist[j],j});
}
}
}
}
int main(){
int s;
cin>>n>>m>>s;
memset(h,-1,sizeof(h));
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
djstl(s);
for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
return 0;
}