dij16分,过#2,用pair

zkhehe @ 2024-10-06 14:41:46

#include <queue>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,s;
int ans[N];
priority_queue<pair<int,int >,vector<pair<int,int> >,greater<pair<int,int> > >pq;//w,u
vector<pair<int,int> >vc[N];//v,w
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        vc[u].push_back(make_pair(v,w));
    }
    pq.push(make_pair(0,s));

    for(int i=1;i<=n;i++){
        int u=pq.top().second;
        int w=pq.top().first;
        if(ans[u]>0)continue;
        ans[u]=w;
        pq.pop();
        for(pair<int,int>p:vc[u]){
            int v=p.first;
            if(ans[v]||v==s)continue;
            int vw=p.second;
            pq.push(make_pair(w+vw,v));
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

by masonxiong @ 2024-10-06 14:43:02

@zkhehe

构造出一组卡掉你的数据：

4 7 1
1 2 1
2 1 1
1 3 1
3 1 1
2 3 1
3 2 1
3 4 100

正确答案应该是 0 1 1 101。

然而您输出 0 1 2 0。

by zkhehe @ 2024-10-06 14:47:16

@masonxiong 感谢数据

by zkhehe @ 2024-10-06 14:50:24

@masonxiong 感谢dalao，过了。没用三角不等式

#include <queue>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,s;
int ans[N];
priority_queue<pair<int,int >,vector<pair<int,int> >,greater<pair<int,int> > >pq;//w,u
vector<pair<int,int> >vc[N];//v,w
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        vc[u].push_back(make_pair(v,w));
    }
    pq.push(make_pair(0,s));

    while(!pq.empty()){
        int u=pq.top().second;
        int w=pq.top().first;
        pq.pop();
        if(ans[u]>0)continue;
        ans[u]=w;
        for(pair<int,int>p:vc[u]){
            int v=p.first;
            if(ans[v]||v==s)continue;
            int vw=p.second;
            pq.push(make_pair(w+vw,v));
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

by zkhehe @ 2024-10-06 14:51:04

@masonxiong 再次感谢数据