dijsktra全部WA，求助

U_star @ 2022-10-15 21:24:08

#include<bits/stdc++.h>
#define inf 2147483647
using namespace std;
int dis[200005],u,v,w,n,m,s;
bool vis[200005];
vector<pair<int,int> >p[200005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void dijsktra()
{
    while(q.empty()==false)
    {
        pair<int,int>k=q.top();
        q.pop();
        if(vis[k.second])
        continue;
        vis[k.second]=1;
        for(int i=p[k.second].size()-1;~i;i--)
        {
            pair<int,int>e=p[k.second][i];
            if(dis[e.second]>k.first+e.first) 
            q.push(make_pair(dis[e.second]=k.first+e.first,e.second));
        }
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    dis[i]=inf;
    for(int i=1;i<=n;i++)
    {
        cin>>u>>v>>w;
        p[u].push_back(make_pair(w,v));
    }
    dis[s]=0;
    q.push(make_pair(0,s));
    dijsktra();
    for(int i=1;i<=n;i++)   
    cout<<dis[i]<<" ";
    return 0;
}

by 凤凰工作室 @ 2022-10-15 21:49:55

给你一份代码

别忘了关注我

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int w[200005],to[200005],ne[200005],h[100005],idx;
int dist[100005];
int n,m,s;
typedef pair<int,int> Pii;
priority_queue<Pii,vector<Pii>,greater<Pii> >heap;
bool vis[100005];
void add(int x,int y,int z)
{
    w[idx]=z;
    to[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}
int main(void)
{
    memset(h,-1,sizeof(h));
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
    }
    memset(dist,0x7f,sizeof(dist));
    dist[s]=0;
    heap.push(make_pair(0,s));
    while(!heap.empty())
    {
        int t=heap.top().second;
        heap.pop();
        if(vis[t])continue;
        vis[t]=true;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=to[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                heap.push(make_pair(dist[j],j));
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<dist[i]<<" ";
    return 0;
}

by U_star @ 2022-10-15 22:25:01

关于我

for(int i=1;i<=m;i++)

写成

for(int i=1;i<=n;i++)

这件事