题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int m,n;
int h[N],e[N],ne[N],indx,w[N];
int dist[N];
int sta[N];
void add(int a,int b,int c){
e[indx]=b,ne[indx]=h[a],w[indx]=c,h[a]=indx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof(dist));
priority_queue<PII,vector<PII>,greater<PII>>heap;
//大根堆priority_queue<int>heap;
dist[1]=0;
heap.push({0,1});
while(heap.size()){
//取点
auto t = heap.top();
heap.pop();
int node=t.second,distance=t.first;
//判断标记
if(sta[node]) continue;
//拓展边
for(int i=h[node];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[node]+w[i]){
dist[j]=dist[node]+w[i];
heap.push({dist[j],j});
}
}
//标记
sta[node]=1;
}
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
scanf("%d %d",&n,&m);
memset(h,-1,sizeof(h));
while(m--){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
}
printf("%d",dijkstra());
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla