样例没过，求调

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

Wei_scky @ 2024-09-18 14:38:21

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int n,m,s;
int dis[N],to[N],w[N],nxt[N],head[N],k;
bool vis[N];
void add(int x,int y,int val) {
    to[k]=y;
    w[k]=val;
    nxt[k]=head[x];
    head[x]=k++;
}
void dijkstra() {
    memset(dis,0x3f,sizeof dis);
//  memset(vis,0,sizeof vis);
    memset(head,-1,sizeof head);
    dis[s]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push({0,s});
    while(!q.empty()) {
        pair<int,int> t=q.top();
        q.pop();
        int v=t.second,cnt=t.first;
        if(vis[v]) continue;
        vis[v]=true;
        for(int i=head[v]; ~i; i=nxt[i]) {
            if(dis[to[i]]>cnt+w[i]) {
                dis[to[i]]=cnt+w[i];
                q.push({dis[to[i]],to[i]});
            }
        }
    }
}
signed main() {
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1; i<=m; i++) {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    dijkstra();
    for(int i=1; i<=n; i++)
        cout<<dis[i]<<" ";
    return 0;
}

by Jarstick @ 2024-09-18 14:39:34

@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇！你太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻！哈哈哈

by kinghku_dzk @ 2024-09-18 14:40:58

@Wei_scky 我太犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇犇！你们太蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻蒻！哈哈哈

by Klayon @ 2024-09-18 14:43:03

by RainBow_doge @ 2024-09-18 14:43:38

by Wei_scky @ 2024-09-18 14:44:26

？？？

by 幻想繁星 @ 2024-09-18 14:45:01

@Wei_scky 你为什么要清空链式前向星

by Teamo_me @ 2024-09-18 14:45:16

by Wei_scky @ 2024-09-18 14:47:36

@幻想繁星谢谢，A了，已关

by Yaakov @ 2024-09-18 14:48:22

by Jarstick @ 2024-09-18 14:48:54

@Wei_scky 当你背极地时阿拉斯加的单词正拂过费城当你解水面时微分的海鸥正跃出方程当你大洋彼岸时晚自习五彩斑斓的夜空散满了鳕鱼

| 下一页