为什么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 回复 分享
发布于 10-11 21:16 江西
本题卡了spfa,spfa的时间复杂度是nm的
点赞 回复 分享
发布于 10-11 21:17 江西
spfa不是死了吗。。
点赞 回复 分享
发布于 10-11 21:48 山东
我dij都被卡T了
点赞 回复 分享
发布于 10-11 21:51 湖北

相关推荐

11-09 14:54
已编辑
华南农业大学 产品经理
大拿老师:这个简历,连手机号码和照片都没打码,那为什么关键要素求职职位就不写呢? 从上往下看,都没看出自己到底是产品经理的简历,还是电子硬件的简历? 这是一个大问题,当然,更大的问题是实习经历的描述是不对的 不要只是去写实习流程,陈平,怎么去开会?怎么去讨论? 面试问的是你的产品功能点,是怎么设计的?也就是要写项目的亮点,有什么功能?这个功能有什么难处?怎么去解决的? 实习流程大家都一样,没什么优势,也没有提问点,没有提问,你就不得分 另外,你要明确你投的是什么职位,如果投的是产品职位,你的项目经历写的全都是跟产品无关的,那你的简历就没用 你的面试官必然是一个资深的产品经理,他不会去问那些计算机类的编程项目 所以这种四不像的简历,在校招是大忌
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务