模板题，求调，悬赏关注

Yzj2010小号 @ 2023-10-20 11:26:35

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define dep(a,b,c) for(int a=b;a>=c;--a)
#define MAX(a,b,c) max(max(a,b),c)
#define MIN(a,b,c) min(min(a,b),c)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
const int N = 2e6+7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int n,m,s,t;
struct edge{
    int v,w;
};
vector < edge > e[N];
int d[N];
bool p[N];
priority_queue< pair < int , int > > q;
inline void dijkstra()
{
    memset(d,inf,sizeof(d));
    memset(p,false,sizeof(p));
    d[s]=0;
    q.push(make_pair(s,0));
    while(!q.empty())
    {
        int f=q.top().first;
        q.pop();
        if(p[f]==true) continue;
        p[f]=true;
        rep(i,0,e[f].size()-1)
        {
            int nex=e[f][i].v;
            if(d[f]+e[f][i].w<d[nex])
            {
                d[nex]=d[f]+e[f][i].w;
                if(!p[nex]) q.push(make_pair(nex,-d[nex]));
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s;
    rep(i,1,m)
    {
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
    }
    dijkstra();
    rep(i,1,n)
    {
        if(d[i]==inf) cout<<"2147483647 ";
        else cout<<d[i]<<" ";
    }
    return 0;
}

by only_a_speaker @ 2023-10-20 11:30:39

您好， std::pair 的排序第一关键字为 first ，第二关键字为 second 。建议调换两个成员的内容

by Yzj2010小号 @ 2023-10-21 06:46:08

@only_a_speaker 谢谢，小号已关注。但还是RE呢！

#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define dep(a,b,c) for(int a=b;a>=c;--a)
#define MAX(a,b,c) max(max(a,b),c)
#define MIN(a,b,c) min(min(a,b),c)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
const int N = 2e6+7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int n,m,s,t;
struct edge{
    int v,w;
};
vector < edge > e[N];
int d[N];
bool p[N];
priority_queue< pair < int , int > > q;
inline void dijkstra()
{
    memset(d,inf,sizeof(d));
    memset(p,false,sizeof(p));
    d[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        int f=q.top().second;
        q.pop();
        if(p[f]==true) continue;
        p[f]=true;
        rep(i,0,e[f].size()-1)
        {
            int nex=e[f][i].v;
            if(d[f]+e[f][i].w<d[nex])
            {
                d[nex]=d[f]+e[f][i].w;
                if(!p[nex]) q.push(make_pair(-d[nex],nex));
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>s;
    rep(i,1,m)
    {
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
        //e[y].push_back({x,z});
    }
    dijkstra();
    rep(i,1,n)
    {
        if(d[i]==inf) cout<<"2147483647 ";
        else cout<<d[i]<<" ";
    }
    return 0;
}

by only_a_speaker @ 2023-10-21 10:37:38

@Yzj2010小号

您好，不建议写如下代码：

for(int i=0;i<=v.size()-1;i++)

由于 v.size() 为无符号数，若 v 为空，则 v.size()-1 反而会变为一个巨大的正数，而非 -1 。

建议修改为：

for(int i=0;i<v.size();i++)

或者

for(int i=0,iend=v.size()-1;i<=vend;i++)