91分spfa,第二个点wa
  • 板块P1807 最长路
  • 楼主tcdthz
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/24 12:28
  • 上次更新2024/1/24 15:28:46
查看原帖
91分spfa,第二个点wa
671205
tcdthz楼主2024/1/24 12:28

第二个点过不了

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef pair<int, int> PII;
const int N = 1e4+10;
int n,m;
vector<PII>g[N];
int v[N]; //标记i点是否在队列中
int d[N];
void spfa()
{
    queue<int> qu;
    qu.push(1);
    d[1]=0; v[1]=1;
    while(qu.size())
    {
        auto x=qu.front(); qu.pop();
        v[x]=0;
        for(auto [i,j]:g[x])
        {
            if(d[i]<d[x]+j)
            {
                d[i]=d[x]+j;
                if(!v[i]) qu.push(i),v[i]=1;
            }
        }
    }
    if(d[n]==0) cout << "-1" ;
    else cout<<d[n];
}
signed main()
{
    memset(d,0,sizeof d);
    cin>>n>>m;
    while (m -- )
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back(make_pair(b,c));
    }
    spfa();

}
2024/1/24 12:28
加载中...