CCYL Membership Activist

题解 CF20C【Dijkstra?】

2021-07-08 08:57:02


Yes, Dijkstra. Because SPFA has died.


言归正传。
↖这个屑没看题目直接写了个最短路模板 (虽然某种意义上这题就是) ,结果显然惨不忍睹。
需要注意的有以下几点:

  • 题目所求是最短路经过的点,而非最短路长度。(这种错误应该也只有博主这样的屑才会犯了
  • 十年 OI 一场空,不开 long long 见祖宗。

剩下的就是简单的 Djikstra 模板了。
唯一需要特别说明的就是路径记录方式。此处题解区好多大佬选择用 vector 存,但是这个屑觉得 vector 太慢,就自己写了个 DFS:

int prpt[100005];
void putans(int id){
    if(id) putans(prpt[id]),printf("%d ",id);
}

好的,可以上代码了。
注:本题中使用的存图方法为链式前向星,不会使用的读者请自行查找有关资料。

//Luogu-CF20C Solution
//Luogu @Enterpr1se (Userid 363523)
//@_Qijia (Userid 363524) AK IOI!
#include<cstdio>
#include<cstring>
#include<queue>
#define regll register long long
#define regint register int
#define regshort register short
#define _Qijia using
#define AK namespace
#define IOI std
_Qijia AK IOI;
int n,m,u,v,ecnt/*前向星变量*/,last[100005]/*前向星变量*/,prpt[100005]/*记录路径上的点*/;
/*令人想辱骂出题人的*/long long w,dist[100005],temp;
bool vis[100005]; 
struct edge{
    int to,prev;
    long long wei;
} fig[200005];
struct node{
    int id;
    long long di;
    const operator < (const node &tocomp) const {
        return di>tocomp.di;
    }
} curr;
priority_queue<node> pqu;
inline void add(int s,int e,int w){
    ++ecnt;
    fig[ecnt]={e,last[s],w};
    last[s]=ecnt;
    ++ecnt;
    fig[ecnt]={s,last[e],w};
    last[e]=ecnt;
    return;
}
void putans(int id){
    if(id) putans(prpt[id]),printf("%d ",id);
}
signed main(){
    scanf("%d%d",&n,&m);
    for(regint i=1;i<=m;++i) scanf("%d%d%lld",&u,&v,&w),add(u,v,w);
    pqu.push({1,0});
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    //Dijkstra本体的循环 
    while(pqu.size()){
        curr=pqu.top();
        pqu.pop();
        vis[curr.id]=true;
        for(regint i=last[curr.id];i;i=fig[i].prev){
            if(vis[fig[i].to]) continue;
            temp=curr.di+fig[i].wei;
            if(temp<dist[fig[i].to]){
                dist[fig[i].to]=temp;
                pqu.push({fig[i].to,temp});
                prpt[fig[i].to]=curr.id;//本题需要加入的特殊处理:记录上一个点 
            }
        }
    }
    if(prpt[n]/*判断是否有解*/) putans(n);
    else putchar('-'),putchar('1');
    return 0;
}

$\mathtt{Thanks}\text{ }\mathtt{for}\text{ }\mathtt{reading.}$