Loading...

洛谷P2136 拉近距离

check评论:0 条 remove_red_eye浏览量:446 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-15

这道题都说了是找负环了$\text{qwq}$

所以只要有负环,就输出$Forever\ love$就行

然后发现只有$90$,因为忘了不止男孩可以追女孩,女孩也可以追男孩$\text{qwq}$

所有从点$n$再跑一次单源最短路径,$dis[1]$和$dis[n]$取个$min$就好

#include <bits/stdc++.h>
#define int long long
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(int s=1)
{
    priority_queue<int> q;
    memset(dis,0x3f,sizeof(dis));
    q.push(s);
    vis[s]=1;
    cnt[s]=1;
    dis[s]=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;
}
main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
    }
    if(spfa())
    {
        printf("Forever love");
        return 0;
    }
    else
    {
        int k=dis[n];
        spfa(n);
        printf("%lld",min(k,dis[1]));
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名