首页 > 代码库 > HDU3790 最短路径问题 【Dijkstra】

HDU3790 最短路径问题 【Dijkstra】

2024-07-17 04:16:44   219人阅读

最短路径问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13336    Accepted Submission(s): 4072


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
路径相同时应更新最小花费。

#include <stdio.h>
#include <string.h>
#define maxn 1002
#define maxm 100002
#define inf 0x7fffffff

int head[maxn], id;
struct Node{
	int to, cost, dist, next;
} E[maxm << 1];
bool vis[maxn];
int dist[maxn], cost[maxn];

void addEdge(int u, int v, int d, int c)
{
	E[id].to = v; E[id].cost = c; E[id].dist = d;
	E[id].next = head[u]; head[u] = id++;
	E[id].to = u; E[id].cost = c; E[id].dist = d;
	E[id].next = head[v]; head[v] = id++;
}

int getNext(int n)
{
	int i, tmp = inf, u = -1;
	for(i = 1; i <= n; ++i)
		if(!vis[i] && dist[i] < tmp){
			tmp = dist[i]; u = i;
		}
	return u;
}

void Dijkstra(int n, int s, int t)
{
	int u, v, i, count, tmpd, tmpc;
	memset(vis, 0, sizeof(vis));
	memset(dist, 0x7f, sizeof(dist));
	memset(cost, 0x7f, sizeof(cost));
	dist[s] = 0; u = s; cost[s] = 0;
	while(u != -1){
		for(i = head[u]; i != -1; i = E[i].next){
			tmpd = dist[u] + E[i].dist;
			tmpc = cost[u] + E[i].cost;
			v = E[i].to;
			if(tmpd < dist[v]){
				dist[v] = tmpd; cost[v] = tmpc;
			}else if(tmpd == dist[v] && tmpc < cost[v]){
				dist[v] = tmpd; cost[v] = tmpc;
			}
		}
		vis[u] = true;
		if(vis[t]) break;
		u = getNext(n);
	}
}

int main()
{
	int n, m, i, u, v, c, d, s, t;
	while(scanf("%d%d", &n, &m), n || m){
		memset(head, -1, sizeof(head));		
		for(i = id = 0; i < m; ++i){
			scanf("%d%d%d%d", &u, &v, &d, &c);
			addEdge(u, v, d, c);
		}
		scanf("%d%d", &s, &t);
		Dijkstra(n, s, t);
		printf("%d %d\n", dist[t], cost[t]);
	}
	return 0;
}


联系
我们