dijkstra爆零求助

SnowFlavour @ 2024-02-16 21:38:34

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=2e5+10;
const int INF=2e9;
struct node{
    int v,w;
    bool operator <(node a) const{
        return w<a.w;
    }
};
struct edge{
    int v,w;
};
vector<edge>e[N];
long long int d1[N];
bool vis[N];
int n,m,s,t;
void dijk1(){
    for(int i=1;i<=n;i++)d1[i]=INF;
    memset(vis,0,sizeof(vis));
    priority_queue<node>dis;
    d1[s]=0;
    dis.push((node){s,0});
    while(!dis.empty()){
        int x=dis.top().v,mn=dis.top().w;
        dis.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int j=0;j<e[x].size();j++){
            int v=e[x][j].v,w=e[x][j].w;
            if(d1[v]>d1[x]+w){
                d1[v]=d1[x]+w;
                dis.push((node){v,d1[v]});
            }
        }
    }
}
int main(){
    freopen("1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back((edge){v,w});
    }
    dijk1();
    for(int i=1;i<=n;i++)cout<<d1[i]<<" ";
}

by toolazy @ 2024-02-16 21:42:02

艹，好逆天啊哥们儿

• 你 freopen？

• 老生常谈hhh，优先队列的比较符重载要反过来写hhh

by toolazy @ 2024-02-16 21:43:28

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=2e5+10;
const int INF=2e9;
struct node{
    int v,w;
    bool operator <(node a) const{
//          return w<a.w;
        return w>a.w;
    }
};
struct edge{
    int v,w;
};
vector<edge>e[N];
long long int d1[N];
bool vis[N];
int n,m,s,t;
void dijk1(){
    for(int i=1;i<=n;i++)d1[i]=INF;
    memset(vis,0,sizeof(vis));
    priority_queue<node>dis;
    d1[s]=0;
    dis.push((node){s,0});
    while(!dis.empty()){
        int x=dis.top().v,mn=dis.top().w;
        dis.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int j=0;j<e[x].size();j++){
            int v=e[x][j].v,w=e[x][j].w;
            if(d1[v]>d1[x]+w){
                d1[v]=d1[x]+w;
                dis.push((node){v,d1[v]});
            }
        }
    }
}
int main(){
//  freopen("1.in","r",stdin);// huh?
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back((edge){v,w});
    }
    dijk1();
    for(int i=1;i<=n;i++)cout<<d1[i]<<" ";
}

by Tachibana27 @ 2024-02-16 21:57:31

freopen("1.in","r",stdin);

乐

by 凌日潮汐 @ 2024-02-16 22:01:35

@zhuo100204 freopen删了，重载运算符反过来写

by SnowFlavour @ 2024-02-17 09:15:03

freopen我试样例用的……好嘞我试试@PatrickChen

by SnowFlavour @ 2024-02-17 09:19:03

好嘞过了，谢谢dalao（鬼知道为什么我会错这样低级的东西）