这是怎么做到的
查看原帖
这是怎么做到的
552688
clx201022楼主2023/10/28 23:41
#include <bits/stdc++.h>
using namespace std;
#ifndef INT_MAX
#define INT_MAX 2147483647
#endif
struct edge
{
    int v, w;
};
bool shortest_distance(int start, int n, vector<int> &dis,vector<edge> e[])
{
    queue<int> q;
    vector<bool> visiting(n + 1,false);
    int count1 = 0;
    dis[start] = 0;
    q.push(start);
    visiting[start] = true;
    while (!q.empty())
    {
        if (count1++ > n - 1) // relax n-1
            return false;
        //不存在负环,最短路最长 n-1
        auto zzz = q.front();
        q.pop();
        visiting[zzz] = false;
        for (auto i : e[zzz])
        {
            if (dis[i.v] > dis[zzz] + i.w) // relax
            {
                dis[i.v] = dis[zzz] + i.w;
                if (!visiting[i.v])
                {
                    q.push(i.v);
                    visiting[i.v] = true;
                }
            }
        }
    }
    return true;
}
vector<edge> e1[1001];
vector<int> distance1;
vector<int> distance2;
int n, m,start=1;
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)e1[i].clear();
    for (int i = 1, s, t, w; i <=m; i++)
    {
        cin >> s >> t >> w;
        e1[s].push_back(edge{t, -w});
    }
    distance1.resize(n+1);
    for(auto &i:distance1)i=INT_MAX;
  /*distance2.resize(n+1);
    for(auto &i:distance2)i=INT_MAX;*/
    start=1;
    if(!shortest_distance(start, n, distance1,e1))
    {
        cout<<"Forever love";
        return 0;
    }
    start=n;
    if(!shortest_distance(start, n, distance2,e1))
    {
        cout<<"Forever love";
        return 0;
    }
    cout<<min(distance1[n],distance2[1]);
    return 0;
}

剩下七个点是怎么做到不 RE 的???

2023/10/28 23:41
加载中...