小红也能拉近距离？（雾）
by dxy2020 @ 2021-10-02 21:09:47
小明可以找小红，小红也可以找小明。
~~可能吧...~~
by QcpyWcpyQ @ 2021-10-02 21:10:27
@[QcpyWcpyQ](/user/450861) @[小小蒟蒻一只](/user/366254)
已过，谢谢。
by Hamer_sans @ 2021-10-02 21:17:53
求助
```
#include<bits/stdc++.h>
using namespace std;
int N,M;
struct edge{
int v;
int w;
int nex;
}Edge[10005];
struct p{
int dis=0x7fffffff;
int dis1=0x7fffffff;
int head;
bool vis;
bool vis1;
int num;
int num1;
}k[1005];
int cnt;
void add(){
int S,T,W;
cin>>S>>T>>W;
Edge[++cnt].v=T;
Edge[cnt].w=-W;
Edge[cnt].nex=k[S].head;
k[S].head=cnt;
return;
}
void spfa(){
priority_queue<pair<int,int> > q;
k[1].dis=0;
k[1].vis=1;
q.push(make_pair(0,1));
while(!q.empty()){
int now=q.top().second;
q.pop();
k[now].vis=0;
if(k[now].num>N){
cout<<"Forever love";
exit(0);
}
for(int br=k[now].head;br;br=Edge[br].nex){
int son=Edge[br].v,w=Edge[br].w;
if(k[son].dis>k[now].dis+w){
k[son].dis=k[now].dis+w;
if(!k[son].vis){
k[son].num++;
q.push(make_pair(-k[son].dis,son));
k[son].vis=1;
}
}
}
}
return;
}
void spfa1(){
priority_queue<pair<int,int> > qq;
k[N].dis1=0;
k[N].vis1=1;
qq.push(make_pair(0,1));
while(!qq.empty()){
int now=qq.top().second;
qq.pop();
k[now].vis1=0;
if(k[now].num1>N){
cout<<"Forever love";
exit(0);
}
for(int br=k[now].head;br;br=Edge[br].nex){
int son=Edge[br].v,w=Edge[br].w;
if(k[son].dis1>k[now].dis1+w){
k[son].dis1=k[now].dis1+w;
if(!k[son].vis1){
k[son].num1++;
qq.push(make_pair(-k[son].dis1,son));
k[son].vis1=1;
}
}
}
}
return;
}
int main(){
cin>>N>>M;
for(int i=1;i<=M;i++){
add();
}
spfa();
spfa1();
cout<<min(k[N].dis,k[1].dis1);
return 0;
}
```
by 00000110hh @ 2022-03-29 18:34:03