题解 CF20C【Dijkstra?】
Enterpr1se
2021-07-08 08:57:02
Yes, Dijkstra. ~~Because SPFA has died.~~
------------
言归正传。
↖这个屑没看题目直接写了个最短路模板 ~~（虽然某种意义上这题就是）~~ ，结果显然惨不忍睹。
需要注意的有以下几点：
+ 题目所求是最短路经过的点，而非最短路长度。（这种错误应该也只有博主这样的屑才会犯了
+ 十年 OI 一场空，不开 `long long` 见祖宗。
剩下的就是简单的 Djikstra 模板了。
唯一需要特别说明的就是路径记录方式。此处题解区好多大佬选择用 `vector` 存，但是这个屑觉得 `vector` 太慢，就自己写了个 DFS：
```cpp
int prpt[100005];
void putans(int id){
if(id) putans(prpt[id]),printf("%d ",id);
}
```
好的，可以上代码了。
**注：本题中使用的存图方法为链式前向星，不会使用的读者请自行查找有关资料。**
```cpp
//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.}$