这道题卡了我特别久。时间复杂度要压缩，用优先队列（堆）。
1420：Dijkastra(II)
时间限制: 1000 ms 内存限制: 131072 KB
提交数: 1605 通过数: 206
【题目描述】
给定一个无向连通图，求从1到n的最短路。
【输入】
第一行两个整数n,m,代表点数和边数；
接下来m行，每行三个整数s,t,d,代表从s到t有一条长度为d的无向边。
【输出】
输出一个整数表示最短距离。
【输入样例】
2 3
1 2 1
1 2 3
2 2 0
【输出样例】
1
【提示】
【数据规模及约定】
N≤200000,M≤400000,1≤S,T≤N,0≤D≤109
思路：dijkstra＋priority_queue（运用struct）。
代码：
#include <bits/stdc++.h>
using namespace std;
struct node
{
int num;
long long dis;
bool operator >(node y) const
{
return dis>y.dis;
}
};
struct sss
{
int numn,di;
};
priority_queue<node,vector<node>,greater<node> > q; //优先队列，更快速
vector<sss> a[200050];
long long dist[200050];
int n,m,s,t,d;
bool vis[200050];
int main()
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&s,&t,&d);//输入
if(s==t) continue;//去除自环
a[s].push_back((sss)
{
t,d
});
a[t].push_back((sss)
{
s,d
}); //推入邻接表
}
memset(dist,0x7f,sizeof(dist));
dist[1]=0;
vis[1]=1;
q.push((node)
{
1,0
}); //初始化
while(!q.empty())
{
node w=q.top();
q.pop();//取值弹出
int k=w.num;
vis[k]=1;//访问过
for(int i=0; i<a[k].size(); i++) //算一遍
{
int p1=a[k][i].numn,p2=a[k][i].di;//取出
if(!vis[p1]&&dist[k]+p2<dist[p1])
{
dist[p1]=dist[k]+p2;//更新
q.push((node)
{
p1,dist[p1]
}); //推入
}
}
}
cout<<dist[n]<<endl;//输出
return 0;
}
还是有点难度的，希望大家能看懂，也还好懂的。
p.s.附老师代码
今天就到这吧，再见！
