求调最短路（必关

xtr169 @ 2024-11-28 20:17:24

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
using namespace std;
int n,m,s,u,v,w,d[1000005],vis[1000005],pos,y,l;
vector< pair <int,int> > E[1000005];
priority_queue< pair<int,int> > pq;
pair<int,int> now;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) d[i]=1e10;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        E[u].pb(mp(w,v));
    }
    d[s]=0;
    pq.push(mp(0,s));
    while(!pq.empty())
    {
        now=pq.top();pq.pop();
        pos=now.sec;
        if(vis[pos]) continue;
        vis[pos]=1;
        for(int i=0;i<E[pos].size();i++)
        {
            y=E[pos][i].sec;l=E[pos][i].fir;
            if(d[y]>d[pos]+l)
            {
                d[y]=d[pos]+l;
                pq.push(mp(d[y],y));
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}

by __CrossBow_EXE__ @ 2024-11-28 20:18:23

@xtr169 e，这是SPFA？

by __CrossBow_EXE__ @ 2024-11-28 20:19:00

哦是dij+堆

by xtr169 @ 2024-11-28 20:21:04

是的

重点是WA

by xtr169 @ 2024-11-28 20:21:18

而且几乎全WA

by iranai @ 2024-11-28 20:21:57

@xtr169你存边是怎么存的啊？是只存了被指向的点和权值吗

by __CrossBow_EXE__ @ 2024-11-28 20:22:48

@xtr169

这是我写的，我没大有时间看，要不你对照一下？

struct node{
    int v,w;
    friend bool operator< (node x,node y){
        return x.w>y.w;
    }
};
vector<node> G[100005];
void dij(int s){
    for(int i=1;i<=n;i++) ans[i]=INF;
    ans[s]=0;
    priority_queue<node> q;
    q.push((node){s,0});
    while(!q.empty()){
        int u=q.top().v;q.pop();
        if(vis[u]) continue;vis[u]=1;
        for(int i=0;i<G[u].size();i++){
            int v=G[u][i].v,w=G[u][i].w;
            if(ans[v]>ans[u]+w){
                ans[v]=ans[u]+w;
                q.push((node){v,ans[v]});
            }
        }
    }
}

by iranai @ 2024-11-28 20:22:58

哦没看到，我的

by __CrossBow_EXE__ @ 2024-11-28 20:24:05

@xtr169

算了直接给你全部的吧

#include<iostream>
#include<cstring>
#include<queue>
#define N 100005
#define M 200005
using namespace std;
int head[N],num;
int dis[N],vis[N];
int n,m,s,u,v,w;
struct Edge{
    int to,w,nxt;
}e[2*M];
struct node{
    int to,w;
    friend bool operator<(node x,node y){
        return x.w>y.w;
    }
};
void add(int from,int to,int w){
    e[++num]=(Edge){to,w,head[from]};
    head[from]=num;
}
priority_queue<node> q;
void dij(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    vis[s]=1;
    for(int i=head[s];i;i=e[i].nxt){
        dis[e[i].to]=e[i].w;
        q.push((node){e[i].to,e[i].w});
    }
    while(!q.empty()){
        int x=q.top().to;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].nxt){
            if(dis[e[i].to]>dis[x]+e[i].w){
                dis[e[i].to]=dis[x]+e[i].w;
                q.push((node){e[i].to,dis[e[i].to]});
            }
        }
    }
}

int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dij(s);
    for(int i=1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
    return 0;
}

by xtr169 @ 2024-11-28 20:24:41

所以各位什么什么WA

by 立柱已选162534 @ 2024-11-28 20:30:38

@xtr169priority_queue是大根堆，需要考虑将d[y]取反再放入堆中，或者使用priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >