题目分析
稀疏图 使用邻接表的表示方法 –> 堆优化的dijkstra
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
const int N=2e5;
bool st[N];
int dist[N];
int h[N],e[N],w[N],ne[N],idx;
int n,m;
void Init(){
memset(h,-1,sizeof h);
}
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra(){
memset(dist,INF,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII> > heap; // 小根堆
heap.push({0,1}); // 我们要对距离排序。所以不可以写成 heap.push({1,0}) ,因为对pair排序,默认按first 排,若fist同再参考second
while(heap.size()){
PII t=heap.top();
heap.pop();
// 必须现在出队,若放到a处出,出去的可能就不是现在的这个值了
// 因为下面有入队的 而优先队列又会动态更新 排好序,所以我们的对头(最小值)会发生变化
int id=t.second,distance=t.first;
if(st[id]) continue; // id距起点的最短路已经确定。 该行可以不加,但加了时间更短。 本题不加会TLE
st[id]=true;
for(int i=h[id];~i;i=ne[i]){
int j=e[i];
if(dist[j]>distance+w[i]){
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
/* a */
}
if(dist[n]==INF) return -1;
return dist[n];
}
int main(){
Init();
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout<<dijkstra()<<endl;
return 0;
}