为什么前两个测试点AC,后面就WA(下载数据在本地测试没问题)

P4779 【模板】单源最短路径(标准版)

jefferw @ 2022-08-16 16:48:54

为什么前两个测试点AC,后面就WA(下载数据在本地测试没问题),代码:

#include <bits/stdc++.h>
#define MAX 100000
#define INF 4294967295//unsigned int最大能表示的数(2^32-1)
using namespace std;
struct edge
{
    int v;
    int w;
};
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
//表示是一对数,第一个是源点到任意点的距离距离,第二个是它相对应的点的编号
//greater:表示第一个数越小越优先
bool vis[MAX];
unsigned int dis[MAX],n,m,s;//dis:任意点到源点的距离距离
//存入pair的对象
vector<edge> e[MAX];//存储图的边
unsigned int ninf(unsigned int a,unsigned int b)//ninf:解决unsigned中inf加1等于0的问题
{
    if(a==INF||b==INF)return INF;
    else return a+b;
}
int dijk(int s)
{
    dis[s]=0;
    q.push(make_pair(0, s));//0:源点到任意点的距离距离  s:(源)点
    while(!q.empty())
    {
        int now=q.top().second;
        //现在的处理的点(找未加入集合s的dis中距离最小的点)
        q.pop();//删除堆顶的元素(pair对象)
        if(vis[now])continue;//如果vis[now]==1(加入了s),那么就退出这一次的循环
        vis[now]=1;

        //借东风
        for(auto& tmp : e[now])
        {

            if(dis[tmp.v]>ninf(dis[now],tmp.w))//ninf:解决unsigned中inf加1等于0的问题
            {
                dis[tmp.v]=ninf(dis[now],tmp.w);
                q.push(make_pair(dis[tmp.v],tmp.v));
            }
        }
    }
    return 0;
}
int main()
{
    memset(dis,255,sizeof(dis));
    memset(vis,0,sizeof(vis));
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<m;++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        edge tmp;
        tmp.v=v;
        tmp.w=w;
        e[u].push_back(tmp);
    }
    //计算结果
    dijk(s);
    //输出结果
    for(int i=1;i<=n;++i)
    {
        printf("%u ",dis[i]);
    }
}

by Cloote @ 2022-08-16 16:55:04

如果本地测的没问题的话,建议放在洛谷 IDE 上再运行一遍


by 蒟酱 @ 2022-08-16 16:59:28

@jefferw 直接开普通 int,inf 设置成 0x3f3f3f3f


by jefferw @ 2022-08-16 17:14:57

@Arcka

输入数据不合法,请问怎么办?


|