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~~~