求dalao看看qaq

回复帖子

@Decoration 2018-09-14 23:06 回复

本蒟蒻第十个点一直wa,qaq,求dalao看看

#include <bits/stdc++.h>
using namespace std;
int head[1010],dis[1010],vis[1010],cnt[1010],tot;
struct edge
{
    int next,to,dis;
}e[20020];
int n,m;
void add(int u,int v,int dis)
{
    tot++;
    e[tot].to=v;
    e[tot].dis=-dis;
    e[tot].next=head[u];
    head[u]=tot;
}
int spfa()
{
    priority_queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    q.push(1);
    vis[1]=1;
    cnt[1]=1;
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.top();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]>dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                if(!vis[v]) 
                {
                    cnt[v]=cnt[u]+1;
                    if(cnt[v]>n)
                    {
                        return 1;
                    }
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    if(spfa())
    {
        printf("Forever love");
        return 0;
    }
    else
    {
        printf("%d",dis[n]);
    }
}
@LinkedIn 2018-09-15 07:07 回复

所以要从开头和结尾各跑一遍

@disangan233 2018-09-15 08:10 回复

膜拜Decoration巨佬!
不是codesonic让我来的