不正经的存图方式 求调
查看原帖
不正经的存图方式 求调
578004
02Ljh楼主2022/9/5 22:05

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;
}

2022/9/5 22:05
加载中...