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
输入数据不合法,请问怎么办?