Slow Path Finding Algorithm

本文主要是介绍Slow Path Finding Algorithm，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题解

本题使笔者认识到了memset导致超时的痛苦。本题只需要打一个简单的最短路即可，每次将入度为0的点加入队列，去掉与它相连的边，并更新最小值，记住别打memset，这道题专门卡memset。

源码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define MAXM 200005
#define MAXN 100005
using namespace std;
int t,n,m,pre[MAXN][30];
int to[MAXM],nxt[MAXM];
int cp[MAXM];
int head[MAXN],tot;
int degin[MAXN],degout[MAXN];
int dis[MAXN][30],pat[MAXN][30];
bool used[MAXM];
bool cir;
priority_queue<int> q; 
void read(int &x)
{int f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-') f=-1;s=getchar();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;} 
void addEdge(int u,int v,char ch)
{to[++tot]=v;cp[tot]=ch-'a';nxt[tot]=head[u];head[u]=tot;used[tot]=false;
}
int main()
{freopen("spfa.in","r",stdin);freopen("spfa.out","w",stdout);read(t);while(t--){tot=0;//memset(to,0,sizeof(to));//memset(nxt,0,sizeof(nxt));//memset(head,0,sizeof(head));//memset(degin,0,sizeof(degin));//memset(degout,0,sizeof(degout));//memset(cp,0,sizeof(cp));//memset(pre,0,sizeof(pre));read(n);read(m);for(int i=1;i<=n;i++)head[i]=degin[i]=degout[i]=0;for(int i=1;i<=m;i++){int u,v;char c;read(u);read(v);scanf("%c",&c);degin[v]++;degout[u]++;addEdge(v,u,c);}//memset(used,false,sizeof(used));//memset(dis,0,sizeof(dis));//memset(pat,0,sizeof(pat));for(int i=1;i<=n;i++){ if(!degout[i])q.push(i);for(int j=0;j<26;j++)pat[i][j]=1,pre[i][j]=dis[i][j]=0;} cir=false;int maxx=-1,k1=0,k2=0;while(!q.empty()){int t=q.top();q.pop();for(int i=head[t];i;i=nxt[i]){int v=to[i];if(used[i]||!degout[v]){cir=true;break;}used[i]=true;degout[v]--;if(!degout[v]) q.push(v);for(int j=0;j<26;j++)if(dis[t][j]>dis[v][j]){dis[v][j]=dis[t][j];pat[v][j]=pat[t][j]+1;pre[v][j]=t;}if(dis[t][cp[i]]+1>dis[v][cp[i]]){dis[v][cp[i]]=dis[t][cp[i]]+1;pat[v][cp[i]]=pat[t][cp[i]]+1;pre[v][cp[i]]=t;}}if(cir) break; }if(cir){puts("-1");continue;}for(int i=1;i<=n;i++){if(degout[i]){cir=true;break;}if(degin[i]) continue;for(int j=0;j<26;j++)if(dis[i][j]>maxx){maxx=dis[i][j];k1=i,k2=j;}}if(cir){puts("-1");continue;}printf("%d %c %d\n",maxx,k2+'a',pat[k1][k2]);int ii=k1;while(ii){printf("%d ",ii);ii=pre[ii][k2];}puts("");}return 0;
}