DAG,SPFA对但dijkstra不对,求调

P1983 [NOIP2013 普及组] 车站分级

SakurajiamaMai @ 2023-08-07 14:23:04

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=1e4+10;
int n,m,res,p[N],a[N],f[N],level[N];
int e[N],ne[N],h[N],idx;
bool vis[N],mp[M][M];
typedef pair<int,int>pii;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
    priority_queue<pii,vector<pii>,greater<pii>>que;
    que.push({0,0}); level[0]=0;
    while(!que.empty()){
        auto now=que.top(); que.pop();
        int x=now.second,y=now.first;
        if(vis[x]) continue; vis[x]=true;
        for(int i=h[x];i!=-1;i=ne[i]){
            int j=e[i];
            if(level[j]<level[x]+1){
                level[j]=level[x]+1;
                que.push({level[j],j});
            }
        }
    }
}
// void spfa()
// {
//     queue<int>que;
//     que.push(0),level[0]=0,vis[0]=true;
//     while(!que.empty()){
//         int now=que.front(); que.pop();
//         vis[now]=false;
//         for(int i=h[now];~i;i=ne[i]){
//             int j=e[i];
//             if(level[j]<level[now]+1){
//                 level[j]=level[now]+1;
//                 if(!vis[j]) vis[j]=true,que.push(j);
//             }
//         }
//     }
// }

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(level,-0x3f,sizeof level);
    for(int i=0;i<m;i++){
        int x; cin>>x;
        memset(vis,false,sizeof vis);
        for(int j=0;j<x;j++) cin>>a[j],vis[a[j]]=true;
        for(int j=a[0];j<=a[x-1];j++){
            if(vis[j]) continue;
            for(int e=0;e<x;e++)
                if(!mp[a[e]][j]) mp[a[e]][j]=true,add(j,a[e]),p[j]++;
        }
    }
    for(int i=1;i<=n;i++) add(0,i);
    memset(vis,false,sizeof vis);
    dijkstra();
    //spfa();
    for(int i=1;i<=n;i++) res=max(res,level[i]);
    //cout<<res; spfa或dijkstra
    cout<<res+1;
    return 0;
}

by Miss_SGT @ 2023-08-07 14:34:02

这道题不是求最长路的吗(浅浅问一下,没看代码)


by 半只蒟蒻 @ 2023-08-07 14:35:10

@SakurajiamaMai Dij 哪能跑最长路啊


by SakurajiamaMai @ 2023-08-07 14:39:22

好吧谢大佬们,我以为改一下建图方式能求最长路呢,看来是我的问题.有个题解用的矩阵spfa,tle了,评论都在说用dijkstra,看来是我没脑子了QAQ~~~


|