HDU 3790 dij+堆優化（領接表版本和vector版本）

求最短路的同僚求最小花費

闆子題 練習下堆優化的dijstr  

dij+鄰接表 

#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1000000; 
struct Edge{
	int v;
	int w;
	int t;
	int next;
}; 
Edge e[maxn];
struct qnode{
	int u;
	int w;
	int t;
	qnode(int u=0,int w=0,int t=0):u(u),w(w),t(t){}
	 
	bool operator < (const qnode& a) const{
		if(w==a.w)  return t>a.t;
	    else return w>a.w;
    }
};
int dis[maxn];
int vis[maxn];
int tis[maxn];
int head[maxn];
int n,m;
int size;
void adde(int u,int v,int w,int t){
	e[size].v=v;
    e[size].w=w;
    e[size].t=t;
    e[size].next=head[u];
    head[u]=size;
    size++;
}
void dij(int s){
	priority_queue<qnode> q;
	dis[s]=0;
	tis[s]=0;
	
	q.push(qnode(s,0,0));
	
	while(!q.empty()){
		qnode tt=q.top();
		q.pop();
		int u=tt.u;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i!=-1;i=e[i].next){
			int v=e[i].v;
			int w=e[i].w;
			int t=e[i].t;
			if(!vis[v]){
				if(dis[v]>dis[u]+w){
					dis[v]=dis[u]+w;
					tis[v]=tis[u]+t;
					q.push(qnode(v,dis[v],tis[v]));
				}
				else if(dis[v]==dis[u]+w &&tis[v]>tis[u]+t){
					tis[v]=tis[u]+t;
					q.push(qnode(v,dis[v],tis[v]));
				}	
                                  // q.push(qnode(v,dis[v],tis[v])); 放這裡是錯的
			}
	        
		}
	}
}
int main(){
	while(scanf("%d%d",&n,&m)){
		
		if(n==m&&n==0) break;
		size=1;
		for(int i=1;i<=n;i++){
			tis[i]=inf;
			dis[i]=inf;
			head[i]=-1;
			vis[i]=0;
		}
		while(m--){
			int x,y,z,c;
			scanf("%d%d%d%d",&x,&y,&z,&c);
			adde(x,y,z,c);
			adde(y,x,z,c);
		}
		int x,y;
		scanf("%d%d",&x,&y);
		dij(x);

		printf("%d %d\n",dis[y],tis[y]);
     
	 }
	 return 0;
	}

           

dij+vector  比上面慢30ms

#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=10000;
struct edge{
	int v;
	int w;
	int t;
	edge(int v=0,int w=0,int t=0):v(v),w(w),t(t){}
};
vector<edge> e[maxn];
struct qnode{
	int u;
	int w;
	int t;
	
	qnode(int u=0,int w=0,int t=0):u(u),w(w),t(t){}
	
	bool operator < (const qnode& a) const{
	if(w==a.w ) return t>a.t;
	else return w>a.w;
	}
};
int dis[maxn];
int tis[maxn];
int n,m;
void dij(int s){
	priority_queue<qnode> q;
	for(int i=1;i<=n;i++){
		dis[i]=inf;
		tis[i]=inf;
	}
	dis[s]=0;
	tis[s]=0;
	q.push(qnode(s,0,0));
	qnode tmp;
	while(!q.empty()){
		tmp=q.top();
		int u=tmp.u;
		q.pop();
		int size=e[u].size();
		for(int i=0;i<size;i++){
			int v=e[u][i].v;
			int w=e[u][i].w;
			int t=e[u][i].t;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				tis[v]=tis[u]+t;
				q.push(qnode(v,dis[v],tis[v]));
			}
			else  if(dis[v]==dis[u]+w&&tis[v]>tis[u]+t){
				tis[v]=tis[u]+t;
				q.push(qnode(v,dis[v],tis[v]));
			}
			
		}
	}
	
}
int main(){
	while(scanf("%d%d",&n,&m)){
		if(n==0&&n==m) break;
		for(int i=0;i<=n;i++){//必須 加 ！！！ 
			e[i].clear();
		}
		while(m--){
			int x,y,z,c;
			scanf("%d%d%d%d",&x,&y,&z,&c);
			e[x].push_back(edge(y,z,c));
			e[y].push_back(edge(x,z,c));
		}
		int x,y;
		scanf("%d%d",&x,&y);
		dij(x);

         printf("%d %d\n",dis[y],tis[y]);
		
		
		
	}
	
	
	
	
	
}