SPFA求指错

@诸葛村夫 2019-05-16 16:57 回复
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
#include<bits/stdc++.h>
using namespace std;
int read()
{
    int kk(0);
    bool fh=true;
    char ch=getchar();
    for(;ch<'0'||ch>'9';)
    {
        if(ch=='-')fh=false;
        ch=getchar();
    }
    for(;ch>='0'&&ch<='9';)
    {
        kk=(kk<<3)+(kk<<1)+(ch^48);
        ch=getchar();
    }
    return fh?kk:-kk;
}
long long readll()
{
    long long kk(0);
    bool fh=true;
    char ch=getchar();
    for(;ch<'0'||ch>'9';)
    {
        if(ch=='-')fh=false;
        ch=getchar();
    }
    for(;ch>='0'&&ch<='9';)
    {
        kk=(kk<<3)+(kk<<1)+(ch^48);
        ch=getchar();
    }
    return fh?kk:-kk;
}
#define INF 214748364
#define MOD 1000000007
#define MAXN
/*struct qnode
{
    int v,c;
    qnode(int _v=0,int _c=0):v(_v),c(_c){};
    bool operator <(const qnode &r) const
    {
        return c>r.c;
    }
};*/
struct Edge
{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){};
};
vector<Edge> edge[1501];
int dis[1501],cnt[1501];
bool vis[1501],inq[1501];
int n,m,u,v,w;

void SPFA(int n,int st)
{
    queue<int>q;
    memset(inq,false,sizeof(inq));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++)dis[i]=INF;
    dis[st]=0;
    inq[st]=1;
    q.push(st);
    for(;!q.empty();)
    {
        int u=q.front();
        q.pop();
        inq[u]=false;
        for(int i=0;i<edge[u].size();i++)
        {
            Edge e=edge[u][i];
            if(/*dis[u]<=INF&&*/dis[e.v]>dis[u]+e.cost)
            {
                dis[e.v]=dis[u]+e.cost;
                if(!inq[e.v])
                {
                    q.push(e.v);
                    inq[e.v]=1;
                    if(++cnt[e.v]>n)return;
                }
            }
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
        edge[read()].push_back(Edge(read(),read()));
    SPFA(n,1);
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。