HDU3790 最短路径问题 【Dijkstra】

最短路径问题

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;
}
           

2015.1.27更新

#include <stdio.h>
#include <string.h>

#define maxn 1002
#define inf 0x3f3f3f3f

int G[maxn][maxn], N;
int Gp[maxn][maxn];
struct Node {
	int d, p;
} D[maxn];
bool vis[maxn];

int getNext() {
	int u = -1, d = inf, p = inf, i;
	for (i = 1; i <= N; ++i)
		if (!vis[i] && D[i].d < d) {
			u = i; d = D[i].d; p = D[i].p;
		} else if (!vis[i] && D[i].d == d && D[i].p > p) {
			u = i; p = D[i].p;
		}
	return u;
}

void Dijkstra(int s, int t) {
	int u = s, i;
	for (i = 1; i <= N; ++i) {
		vis[i] = 0; D[i].d = D[i].p = inf;
	}
	D[u].d = D[u].p = 0;
	while (u != t) {
		vis[u] = 1;
		for (i = 1; i <= N; ++i) {
			if (D[u].d + G[u][i] < D[i].d) {
				D[i].d = D[u].d + G[u][i];
				D[i].p = D[u].p + Gp[u][i];
			} else if (D[i].d == D[u].d + G[u][i] && D[i].p > D[u].p + Gp[u][i])
				D[i].p = D[u].p + Gp[u][i];
		}
		u = getNext();		
	}
	printf("%d %d\n", D[t].d, D[t].p);
}

int main() {
	freopen("stdin.txt", "r", stdin);
	int M, u, v, d, p, s, t;
	int i, j;
	while (scanf("%d%d", &N, &M), N | M) {
		for (i = 1; i <= N; ++i)
			for (j = 1; j <= N; ++j)
				G[i][j] = Gp[i][j] = inf;
		while (M--) {
			scanf("%d%d%d%d", &u, &v, &d, &p);
			if (G[u][v] > d) {
				G[u][v] = G[v][u] = d; Gp[u][v] = Gp[v][u] = p;
			} else if (G[u][v] == d && Gp[u][v] > p)
				Gp[u][v] = Gp[v][u] = p;
		}
		scanf("%d%d", &s, &t);
		Dijkstra(s, t);
	}
	return 0;
}