蓝桥杯 算法训练 最短路（最短路模板）

• 思路：最短路模板题，出错了一次，没有全部清空导致出错。
  
  
• 代码：
  

  #include<bits/stdc++.h>
  using namespace std;
  
  const int maxn = 200000+10;
  int n,m;
  int d[maxn];
  vector< pair<int,int> > E[maxn];
  
  void init(){
  	for(int i=0;i<maxn;i++)	d[i]=1e9;		
  	for(int i=0;i<maxn;i++)	E[i].clear();
  }
  void dijkstra(){		 
  	d[1]=0;
  	priority_queue< pair<int,int> > q;
  	q.push( make_pair(-d[1],1) );
  	while(!q.empty()){
  		int u=q.top().second;
  		q.pop();
  		for(int i=0;i<E[u].size();i++){
  			int v=E[u][i].first;
  			if(d[v]>d[u]+E[u][i].second){
  				d[v]=d[u]+E[u][i].second;
  				q.push(make_pair(-d[v],v));
  			}
  		}
  	}
  }
  int main(){
  	while(cin>>n>>m){
  		init();
  		for(int i=0;i<m;i++){
  			int a,b,x;
  			cin>>a>>b>>x;
  			E[a].push_back(make_pair(b,x));
  		}
  		dijkstra();
  		for(int i=2;i<=n;i++){
  			printf("%d\n",d[i]);
  		}
  	}	
  	return 0;
  }