[dijkstra] 小木乃伊到我家 长沙理工大学校赛E

长沙理工大学校赛E"/>

[dijkstra] 小木乃伊到我家 长沙理工大学校赛E

链接：

题目描述

AA的欧尼酱qwb是个考古学家，有一天qwb发现了只白白圆圆小小的木乃伊，它是个爱哭鬼却很努力。qwb想把这么可爱的小木乃伊送给
AA，于是便找上了快递姐姐，这下可让快递姐姐犯愁了，因为去往AA家的路实在太难走了（甚至有可能没有路能走到AA家），快递姐姐
找上聪明的ACMer，想请你帮忙找出最快到达AA家的路，你行吗？

输入描述:

第一行输入两个整数n和m（2<=n<=m<=200000），分别表示有n座城市和m条路，城市编号为1~n（快递姐姐所在城市为1，AA所在城市为n）。
接下来m行，每行输入3个整数u,v,w（u,v<=n，w<=100000），分别表示城市u和城市v之间有一条长为w的路。

输出描述:

输出结果占一行，输出快递姐姐到达AA家最短需要走多远的路（及最短路条数），如果没有路能走到AA家，则输出“qwb baka”（不用输出双引号）。

//dijkstra算法的优化：结合向量及优先队列#include <bits/stdc++.h>
using namespace std;
int po[200000];
struct way
{int to;long long int cost;
};//记录vec[起点]的 多个 终点及边长
struct Node
{int hao;long long int lu;
};//用于优先队列排序
vector<way>vec[200001];  
long long int d[200001];  //记录各点最短路
bool operator <(Node a,Node b)
{return a.lu>b.lu;
}  //优先队列优先级 符号相反
priority_queue<Node>que;
void dij()
{while(!que.empty()){Node e=que.top();que.pop();  //当前最短点的信息int L=vec[e.hao].size();   //与e.hao连接的路径数for(int i=0;i<L;i++){way r=vec[e.hao][i];  //依次取出点及其信息if(d[r.to]>d[e.hao]+r.cost)  //更新最短路{d[r.to]=d[e.hao]+r.cost;Node q;q.hao=r.to;q.lu=d[r.to];po[r.to]=po[e.hao];  //更新最短路 最短路条数与e.hao最短路条数相同que.push(q);}else if(d[r.to]==d[e.hao]+r.cost) //相同时{po[r.to]+=po[e.hao];  //增加最短路条数}}}
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=m;i++){way w,y;long long int a,b,c;cin>>a>>b>>c;w.to=b;w.cost=c;y.to=a;y.cost=c;vec[a].push_back(w);vec[b].push_back(y);//双向路径 //vector 可变数组；二维数组空间超限}for(int i=2;i<=n;i++) d[i]=1e18;  //求最短，初始设为无穷大d[1]=0;  //初始化po[1]=1;  //初始路径条数设为1Node no;no.hao=1;no.lu=0;que.push(no);  //起始点信息dij();if(d[n]==1e18) cout<<"qwb baka"<<endl;else cout<<d[n]<<' '<<po[n]<<endl;return 0;
}