题目描述
样例
blablabla
算法1
时间复杂度
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5;
typedef pair<int, int> pii;//用于优先队列存数据,同时保存最小距离和哪个点
int d[N];//每个点到1的距离
int n,m;
priority_queue<pii,vector<pii>,greater<pii>> q;//first = d,second = t
int h[N],e[N],ne[N],w[N],idx;//邻接表
int st[N];//判断该点是不是已经使用过了
void add(int a,int b,int c)
{
w[idx] = c,e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void dijkstra()
{
memset(d,0x3f,sizeof d);// 初始化d
d[1] = 0;
q.push({0,1});
while (q.size())
{
auto t = q.top();q.pop();
int k = t.second,dis = t.first;
if (st[k])continue;//如果该点已经处理过,则说明该点最小距离已经确定,直接跳过
st[k] = 1;//到这里说明该点没处理过,那就是目前的最小值,标记成处理过
for (int i = h[k];i != -1;i = ne[i])//遍历目前最小点的所有邻点,更新距离
{
int j = e[i];//i相当于表示idx,e[idx]就是邻点编号
if (d[j] > dis + w[i])//w[idx]就是k点到j点的权重
{
//printf ("%d ",j);
d[j] = dis +w[i];//如果当前距离被更新则把当前点加入堆中
q.push({d[j],j});
}
}
}
}
int main()
{
cin >> n >> m;
memset(h,-1,sizeof h);
while (m -- )
{
int a,b,c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
if (d[n] > 0x3f3f3f3f/2)printf ("-1");
else printf ("%d",d[n]);
return 0;
}