HDU 3790 最短路径问题（单源最短路---Dijkstra算法）

清疚 2024-02-17 20:52 26阅读 0赞

## 最短路径问题 ##

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 25591 Accepted Submission(s): 7638**

Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。  
(1<n<=1000, 0<m<100000, s != t)

Output

输出 一行有两个数， 最短距离及其花费。

Sample Input

3 2
    1 2 5 6
    2 3 4 5
    1 3
    0 0

Sample Output

9 11

分析：用的是Dijkstra的mlogn算法，和以前做的最短路的区别在于多了个最短路相同时选择开销最少的，那很好办，首先用到优先队列，重写<运算符，在进入队列时多加一个==判断（d\[e.to\]>=d\[e.from\]+e.d），这是因为，两点之间可能有重复的路径，当他们的d值相同，但开销不同，如果没有=号，那么当d相同时，开销大的去更新d值，那么遇到开销小的就无法去更新d值了，所以加上=之后就进入队列，通过优先队列选择；也不用麻烦在输入的时候更新边的关系，多条边重复也没关系。和一般的最短路就这点差别。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<vector>
    #include<queue>
    using namespace std;
    #define INF 1000000
    const int maxn=1000+10;
    struct Edges{
    	int from,to,d,p;
    	Edges(int from=0,int to=0,int d=0,int p=0):from(from),to(to),d(d),p(p){}
    };
    vector<Edges>edges;
    vector<int>g[maxn];
    int n,m;
    int vis[maxn];
    int d[maxn];
    int last;
    
    struct node{
    	int u,d,p; //节点u，起始节点到当前节点的距离、以及开销 
    	node(int u=0,int d=0,int p=0):u(u),d(d),p(p){} 
    	bool operator < (const node& nt)const {
    	if(d>nt.d)return true;
    	if(d==nt.d && p>nt.p)return true;
    	return false ;
    	}
    };
    
    void dijkstra(int first){
    	memset(vis,0,sizeof(vis));
    	priority_queue<node>q;
    	q.push(node(first,0,0));
    	for(int i=1;i<=n;i++)d[i]=INF;
    	d[first]=0;
    	
    	while(!q.empty()){
    		node v=q.top();q.pop();
    		int u=v.u;
    		if(u==last){
    			printf("%d %d\n",v.d,v.p);
    			return ;
    		}
    		
    		if(vis[u])continue;
    		vis[u]=1;
    		
    		
    		for(int i=0;i<g[u].size();i++){
    			Edges e=edges[g[u][i]];
    			if(d[e.to]>=d[e.from]+e.d ){   //这不要忘了=，因为两点之间可能有多条路径，长度相同选择消费最小的，这么没注意到WA了一次 
    				d[e.to]=d[e.from]+e.d;
    				q.push(node(e.to,d[e.to],v.p+e.p));	
    			}
    		}
    	}
    }
    int main(){
        while(scanf("%d%d",&n,&m)==2 && n){
        	int a,b,d,p;
        	for(int i=0;i<m;i++)
        	{
        		scanf("%d%d%d%d",&a,&b,&d,&p);
        		edges.push_back(Edges(a,b,d,p));
        		int l=edges.size();
        		edges.push_back(Edges(b,a,d,p));
        		g[a].push_back(l-1);
        		g[b].push_back(l);
    		}
        	
        	int first;
        	scanf("%d%d",&first,&last);
        	dijkstra(first);
        	
        	for(int i=0;i<n;i++)g[i].clear(); //清空容器 
        	edges.clear();
    	}	
    	return 0;
    }

附带一组数据：

5 7  
1 2 5 5  
2 3 4 5  
1 3 4 6  
3 4 2 2  
3 5 4 7  
4 5 2 4  
1 3 4 4  
1 5  
8 10