MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 CF20C 【Dijkstra?】

posted on 2018-03-29 18:43:28 | under 题解 |
  • 刚开始看以为是最短路的模板题,就直接用堆优化dijkstra+输出路径搞了一波。结果十分惨烈……

这道题坑还是有的,比如:

  • 边是双向边(这一点翻译没有很好的说明)
  • 后边的数据大到要开long long

知道了这些后,这题就比较简单了,直接最短路+路径输出 就可以了

在下用的是堆优化dijkstra

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
struct yyy{
    int f,
        t,
        len,
        nex;
}e[500100*2]; //前向星存图 
struct node{
    int x; long long y;
    bool operator < (const node& hhh) const{ return y>hhh.y; } //重载运算符实现小根堆 
}; 
priority_queue <node> q; //STL大法好 
int tot,head[100100];
void add(int x,int y,int z) //加边函数 
{
    e[++tot].f=x;
    e[tot].t=y;
    e[tot].len=z;
    e[tot].nex=head[x];
    head[x]=tot;
}
long long int dis[100100]; //一定要开long long 
int flag,ans[100100],pos[100100]; //存储路径 
int main()
{
    int n,m,s;
    cin>>n>>m; s=1;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z); //双向边 
        add(y,x,z);
    }
    for(int i=1;i<=n;i++)
      dis[i]=9223372036854775806;
    dis[s]=0; ans[flag]=s;
    q.push(node{s,dis[s]});
    while(!q.empty())  //dijkstra主体 
    {
        node ww=q.top(); q.pop();
        int k=ww.x;
        if(ww.y!=dis[k]) continue;
        for(int j=head[k];j;j=e[j].nex)
          if(dis[e[j].t]>dis[k]+e[j].len)
          {
            dis[e[j].t]=dis[k]+e[j].len;
            q.push(node{e[j].t,dis[e[j].t]});
            pos[e[j].t]=k; //存储路径 
          }
    }
    bool flag2=1; //判断能否找到起点 
    for(int i=n;i;i=pos[i]) //到着从终点找回去
    {
        ans[++flag]=i;
        if(i==1) //如果找到起点,更改判断变量 
          flag2=0;
    }

    if(flag2){
        cout<<-1; return 0;
    } //没有找到起点,输出"-1"

    for(int i=flag;i>=1;i--) //因为是倒着找回去的,所以要倒序输出 
      cout<<ans[i]<<" ";
    return 0;
}