按照题解第一篇改了我自己的代码为什么还是90?求助
  • 板块P2136 拉近距离
  • 楼主dk_qwq
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/6/24 05:54
  • 上次更新2023/10/27 22:43:38
查看原帖
按照题解第一篇改了我自己的代码为什么还是90?求助
311306
dk_qwq楼主2022/6/24 05:54

rt

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1e3+5;
struct edge{
    int v,w;
};
vector<edge>e[maxn];
int n,m;
int dis[maxn],cnt[maxn];
bool vis[maxn];
queue<int>q;
bool spfa(int s){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[s]=0,vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop(),vis[u]=0;
        if(u==n){
            continue;
        }
        for(auto ed:e[u]){
            int v=ed.v,w=ed.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n){
                    printf("Forever love");
                    exit(0);
                }
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    while(m--){
        int s,t,w;
        scanf("%d%d%d",&s,&t,&w);
        e[s].push_back({t,w*(-1)});
    }
    spfa(1);
    int ans=dis[n];
    while(!q.empty()){
        q.pop();
    }
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    spfa(n);
    printf("%d",min(ans,dis[1]));
}
2022/6/24 05:54
加载中...