不正经的存图方式求调

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

02Ljh @ 2022-09-05 22:05:33

Rt 板子会打但Edge学不明白

自己打了一份不正经的存图方式样例过了 but 0pts

求大佬指出这种方式的不合理性

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define MAXN 10019
struct l
{
    vector<int> bq;//连向的边
    vector<int> vq;//边权
} all[MAXN];
struct lx
{
    int pos,w;
    friend bool operator <(lx x,lx y)
    {
        return x.w<y.w;
    }
} temp;
priority_queue<lx> q;
int dis[MAXN];
bool vi[MAXN];
int n,m,s;
void dij()
{
    while(!q.empty())
    {
        int now=q.top().pos;
        q.pop();
        if(vi[now]) continue;
        vi[now]=true;
        for(int i=0;i<all[now].bq.size();i++)
        {
            dis[all[now].bq[i]]=min(dis[all[now].bq[i]],dis[now]+all[now].vq[i]);
            //cout<<"dis["<<all[now].bq[i]<<"]="<<dis[all[now].bq[i]]<<"\n";
            temp.pos=all[now].bq[i];
            temp.w=all[now].vq[i];
            q.push(temp);
        }
    }
    return ;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        all[u].bq.push_back(v);
        all[u].vq.push_back(w);
    }
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    temp.pos=s;
    temp.w=0;
    q.push(temp);
    dij();
    for(int i=1;i<=n;i++) cout<<(dis[i]==INF?2147483647:dis[i])<<" ";
    return 0;
}

by Kanbe_Kotori @ 2022-09-05 22:16:48

存图方式感觉没啥问题，应该是其他地方写错了

by _djc_ @ 2022-09-05 23:14:50

阿哲……您的代码看起来好废命……

楼上大佬说了不是存图的问题

首先是 dijkstra 写的不对，更新 dis 一定是在当前 dis 不是最优的时候在队列里加入状态

第二点是您优先队列里的状态不对，对于堆中的状态我们不是选他边权最小的，而是选 dis 最小的（雾

最后一点就是您的重载运算符写错了……（找了好半天，大雾

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define MAXN 500019
struct l
{
    vector<int> bq;//连向的边
    vector<int> vq;//边权
} all[MAXN];
struct lx
{
    int pos,w;
    bool operator <(const lx &x)const
    {
        return x.w<w;
    }
} temp;
priority_queue<lx> q;
int dis[MAXN];
bool vi[MAXN];
int n,m,s;
void dij()
{
    while(!q.empty())
    {
        int now=q.top().pos;
        q.pop();
        if(vi[now]) continue;
        vi[now]=true;
        for(int i=0;i<all[now].bq.size();i++)
        {
            if(dis[all[now].bq[i]] > dis[now]+all[now].vq[i]){
                dis[all[now].bq[i]] = dis[now]+all[now].vq[i];
                temp.pos=all[now].bq[i];
                temp.w=dis[all[now].bq[i]];
                q.push(temp);
            }
            //cout<<"dis["<<all[now].bq[i]<<"]="<<dis[all[now].bq[i]]<<"\n";

        }
    }
    return ;
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        all[u].bq.push_back(v);
        all[u].vq.push_back(w);
    }
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    temp.pos=s;
    temp.w=0;
    q.push(temp);
    dij();
    for(int i=1;i<=n;i++) cout<<(dis[i]==INF?2147483647:dis[i])<<" ";
    return 0;
}

by 02Ljh @ 2022-09-06 20:09:57

@Di_jcheng @o_scary_ang

谢谢大佬们 Orz %%%

~~主要是 Edge 实在没理解~~

不正经的存图方式 求调

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

不正经的存图方式求调