为什么D题跑SPFA过不了

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=2e5+100,M=3e5+100;
#define endl '\n'
ll dp[N][11];
ll w[N];
int n,k,m;
int h[N],ne[M<<1],e[M<<1],idx;
bool vis[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        fill(h,h+n+20,-1);
        fill(vis,vis+n+20,0);
        idx=0;
        for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=1e18;
        //memset(vis,0,sizeof vis);
        //memset(h,-1,sizeof h);
        for(int i=1;i<=n;i++)cin>>w[i];
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }
        queue<int>q;
        q.push(1);
        if(k>0);
        dp[1][1]=1;
        dp[1][0]=w[1];
        vis[1]=1;
        while(q.size())
        {
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=h[u];~i;i=ne[i])
            {
                int j=e[i];
                for(int o=0;o<=k;o++)
                {
                        if(dp[j][o]>dp[u][o]+w[j])
                        {
                            dp[j][o]=dp[u][o]+w[j];
                            if(!vis[j])vis[j]=1,q.push(j);
                        }
                        if(o>=1)
                        if(dp[j][o]>dp[u][o-1]+1)
                        {
                            dp[j][o]=dp[u][o-1]+1;
                            if(!vis[j])vis[j]=1,q.push(j);
                        }
                       // dp[j][o]=min(dp[j][o],dp[u][o]+w[j]);
                }
            }
        }
        ll ans=1e18;
        for(int i=0;i<=k;i++)ans=min(ans,dp[n][i]);
        cout<<ans<<endl;
    }
    return 0;
}

全部评论
qp
1 回复 分享
发布于 2024-10-11 21:16 江西
我dij都被卡T了
点赞 回复 分享
发布于 2024-10-11 21:51 湖北
spfa不是死了吗。。
点赞 回复 分享
发布于 2024-10-11 21:48 山东
本题卡了spfa,spfa的时间复杂度是nm的
点赞 回复 分享
发布于 2024-10-11 21:17 江西

相关推荐

不愿透露姓名的神秘牛友
07-11 15:37
点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
06-15 20:57
已编辑
门头沟学院 Java
CARLJOSEPH...:年轻人有傲气很正常,但是建议工作前洗净傲气。 说实在的,什么奖学金什么奖项的都很一般。尊重你的老师,在有时间的时候去上课,真遇到走不开的事,请态度端正地向你的老师说明情况,请求请假。我相信任何一个有师德的老师都会允许的(我的老师就是这样)。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-11 11:24
大家还是用ai改吧,我心疼得要死,就当花钱买教训吧,人家直接拿完钱就跑路了
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务