历史遗留问题
  • 板块学术版
  • 楼主Molmin
  • 当前回复10
  • 已保存回复10
  • 发布时间2021/4/25 19:44
  • 上次更新2023/11/5 00:08:00
查看原帖
历史遗留问题
478528
Molmin楼主2021/4/25 19:44

为什么第67行改成<1e15就对了?

#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
   long long s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(long long x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const long long maxn=1e5+5;
long long dis[maxn],bak[maxn],i,k,n,m,u[maxn],v[maxn],w[maxn],check,flag,inf=LONG_LONG_MAX/2-2;
int main()
{
    n=read();
    m=read();
    for(long long i=1;i<=m;i++)
    {
        u[i]=read();
        v[i]=read();
        w[i]=read();
    }
    for(long long i=1;i<=n;i++)
    {
        dis[i]=inf;
    }
    dis[1]=0;
    for(k=1;k<n;k++)
    {
        check=0;
        for(long long i=1;i<=m;i++)
        {
            if(dis[v[i]]>dis[u[i]]+w[i])
            {
                dis[v[i]]=dis[u[i]]+w[i];
                check=1;
            }
        }
        if(!check)
        {
            break;
        }
    }
    flag=0;
    for(long long i=1;i<=m;i++)
    {
        if(dis[v[i]]>dis[u[i]]+w[i])
        {
            flag=1;
            break;
        }
    }
    if(flag)
    {
        puts("Error!");
    }
    else
    {
        for(long long i=1;i<=n;i++)
        {
            if(dis[i]<1e15)
            write(dis[i]);
            else
            {
                printf("inf");
            }
            putchar(' ');
        }
        puts("");
    }
}
2021/4/25 19:44
加载中...