题意

懂得都懂 【狗头

思路

负权有向图最短路(最佳算法-spfa)

极度考验语文阅读理解

特殊点:

• 无限接近 == 出现负环 spfa判负环
• 计算出他们之间可能的最短距离 == 去了再回来 两次spfa

代码

#include<iostream>
#include<cstring>
#include<queue>
#define INF 0x3f
#define N 1005
#define M 114514
//保险做法
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
int n,m;
struct ed
{
    int u,v,w;
    int next;
};
ed edge[M];//使用链式前向星
int h[M],tot;
int dis[M];
int vis[N];
int cnt[N];
queue<int>q;
bool spfa(int s)//记得要带s,到时候就知道了
{
    memset(dis,INF,sizeof dis);
    memset(vis,0,sizeof vis);
    memset(cnt,0,sizeof cnt);
    dis[s]=0;
    q.push(s);
    vis[s]=1;
    while(!q.empty())//spfa基操,不必多言
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=h[u];i;i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n)//出现负环
                {
                    cout<<"Forever love";//输出
                    return 1;//结束
                }
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    cin>>n>>m;//输入
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;//输入
        edge[++tot]={u,v,-w,h[u]};//记得要取相反数
        h[u]=tot;
    }
    int mi;
    if(spfa(1))return 0;//小明->小红
    mi=dis[n];
    if(spfa(n))return 0;//小红->小明
    mi=min(dis[1],mi);//取最小的
    cout<<mi;//输出
    return 0;//完结散花
}