题解 P2832 【行路难】

y2823774827y · 2018-10-03 08:43:54 · 题解

貌似下面的题解已全被hack

分析 dalao就直接看程序吧

1. 采用的是普通的bfs入队列，正确性？先是不太疲劳时会直接入队列；后面来的情况必须是当前路径小于之前确定的才有可能为解：因为已经更疲劳了，路径总得小点吧(对同一点入队列分析)
2. 该题主要难点其实在于如何存入路径，每个点的前驱会随bfs更新而变化，所以本题这样似乎行不通留给dalao们尝试吧，一般spfa_bfs都习惯用标准queue存入点。这里自己定义队列，用结构体去维护值

ps：由于蒟蒻能力有限，如有hack数据希望私信

//n<=10000, m<=200000
#include<cstdio>
#include<cstring>
using namespace std;
struct node{
    int to,next,d;
}dis[200010];
struct code{
    int u,d,dfn,pre;
}que[100000010];
int n,m,num,inf=0x3f3f3f3f,tail,hea; int last[10010],head[10010],lu[10010];
inline void add(int u,int v,int d){
    dis[++num].to=v; dis[num].d=d; dis[num].next=head[u]; head[u]=num;
}
void cout(int x){
    if(!x)
        return;
    cout(que[x].pre);
    printf("%d ",que[x].u);
}
void bfs(){
    memset(lu,inf,sizeof(lu));
    lu[1]=0;
    que[++tail].u=1;
    while(hea<=tail){
        hea++;
        int u=que[hea].u,dfn=que[hea].dfn,d=que[hea].d;
        for(int i=head[u];i;i=dis[i].next){
            int v=dis[i].to;
            if(lu[v]>d+dfn+dis[i].d){
                lu[v]=d+dfn+dis[i].d;
                tail++;
                que[tail]=(code){v,lu[v],dfn+1,hea};
                last[v]=tail;
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        add(u,v,d);
    }
    bfs();
    printf("%d\n",lu[n]);
    cout(last[n]);
    return 0;
}