題目連結:
https://www.luogu.org/problem/P2136
思路提示部落格:https://www.luogu.org/blog/user27165/solution-p2136
思路:
1:關鍵點:“拉近距離”的不一定是小明,也可能是小紅,題目中沒有給出具體的源點彙點,是以在做spfa的時候,分别以1和n為源點各做一遍,取min
spfa(1);
int mi=d[n];
spfa(n);
cout<<min(mi,d[1])<<endl;
2:判斷負環的方法,cnt數組,存一個節點入隊的次數,如果大于n則說明存在負環
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+1;
vector<pair<int,int> >e[maxn];
int n,m,ing[maxn],a,b,c,d[maxn],cnt[maxn];
inline void spfa(int s)
{
memset(ing,0,sizeof(ing));
memset(d,0x7f,sizeof(d));
queue<int>q;
q.push(s);
cnt[s]++;
d[s]=0;
ing[s]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
ing[now]=0;
if(cnt[now]>n)
{
cout<<"Forever love"<<endl;
exit(0);
}
for(int i=0;i<e[now].size();i++)
{
int v=e[now][i].first;
if(d[v]>d[now]+e[now][i].second)
{
d[v]=d[now]+e[now][i].second;
if(ing[v])
continue;
q.push(v);
cnt[v]++;
ing[v]=1;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a>>b>>c;
e[a].push_back(make_pair(b,-c));
}
spfa(1);
int mi=d[n];
spfa(n);
cout<<min(mi,d[1])<<endl;
return 0;
}