[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define NIL 100000
struct Node
{
int d; //記錄最短路徑長度
int m; //記錄最小花費
int pre; //記錄前驅
int flag; //標記所屬集合
}node[1001];
/*
初始化操作，把源點初始化為0，其他正無窮
@param n 結點個數
@param s 源點
*/
int init_shortpath_source(int n, int s)
{
int i = 1;
for(i = 1; i <= n; ++i)
{
node[i].d = NIL; //開始置最短路徑為正無窮
node[i].m = NIL; //最小花費為正無窮
node[i].flag = 0; //所屬 0 集合
node[i].pre = 0; //前驅為 0
}
node[s].d = 0; //源點最短路徑置為 0
node[s].m = 0;//最小花費置為 0
return 1;
}
/*松弛操作
*@param u 路徑起始點
*@param v 路徑結束點
*@param gp 路徑圖
*@param gm 花費圖
*/
int relax(int u, int v, int** gp, int** gm)
{
if(node[v].d > node[u].d + gp[u][v]) //對路徑進行松弛
{
node[v].d = node[u].d + gp[u][v];
node[v].m = node[u].m + gm[u][v];
node[v].pre = u;
}
else if(node[v].d == node[u].d + gp[u][v]) //對花費進行松弛
{
if(node[v].m >= node[u].m + gm[u][v])
{
node[v].d = node[u].d + gp[u][v];
node[v].m = node[u].m + gm[u][v];
node[v].pre = u;
}
}
return 1;
}
/*申請二維數組空間， 大小為n*n
@param n 二維數組空間的 大小
@result 返回一個 (n+1)*(n+1) 大小的 二維數組，下標從1開始到n
*/
int** apply_malloc(int n)
{
int **p;
int i;
p = (int**)malloc(sizeof(int)*(n+1));
for(i = 0; i<=n; ++i)
{
p[i] = (int *)malloc(sizeof(int)*(n+1));
}
return p;
}
/*初始化二維數組
@param gp 存儲路徑權值
@param gm 存儲花費權值
*/
int init(int **gp, int **gm, int n)
{
int i = 1,j = 1;
for(i = 1;i <= n; ++i)
{
for(j = i; j <= n; ++j)
{
gp[i][j] = NIL;
gp[j][i] = NIL;
gm[i][j] = NIL;
gm[j][i] = NIL;
}
}
return 1;
}
/**
Dijkstra 算法
*/
int dijkstra(int ** gp, int ** gm, int s, int n)
{
int flag = n;
int index = 0;
int i,j,min;
init_shortpath_source(n,s);
while(flag--)
{
/*查找集合 0 中，路徑上界最小的結點*/
for(i = 1; i <= n; ++i)
{
if(node[i].flag == 0)
{
min = node[i].d;
index = i;
break;
}
}
for(++i; i <= n; ++i)
{
if(node[i].flag == 0 && min > node[i].d)
{
min = node[i].d;
index = i;
}
}
/*將該點 加入 1 集合*/
node[index].flag = 1;
/*對每個以該點為起點的路徑進行松弛操作*/
for(j = 1; j <= n; ++j)
{
if(node[j].flag == 0 && gp[index][j] != NIL)
{
relax(index,j,gp,gm);
}
}
}
return 1;
}
/*打印一個二維數組*/
int printf_array_2(int ** array, int n)
{
int i,j;
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= n; ++j)
{
printf("%d\t", array[i][j]);
}
printf("\n");
}
return 1;
}
/*主方法*/
int main()
{
int n,m,a,b,p,q,i,s,e;
int **gp, **gm;
/*輸入 結點個數， */
scanf("%d%d",&n,&m);
while(n||m)
{
/*申請兩個二維數組空間， 一個存放路徑權值， 一個存放花費權值*/
gp = apply_malloc(n);
gm = apply_malloc(n);
/*初始化二維表*/
init(gp,gm,n);
for(i = 1; i <= m; ++i)
{
/*輸入路徑和花費*/
scanf("%d%d%d%d",&a,&b,&p,&q);
/*解決有多條路徑的問題，取權值最小的一條路徑進行運算*/
if(gp[a][b] > p)
{
gp[a][b] = p;
gm[a][b] = q;
gp[b][a] = p;
gm[b][a] = q;
}
/*解決多條路徑具有相同權值問題，取花費最小的一條路徑進行運算*/
else if(gp[a][b] == p && gm[a][b] > q)
{
gm[a][b] = q;
gm[b][a] = q;
}
}
/*輸入源點和終點*/
scanf("%d%d",&s,&e);
/*進行Dijkstra運算*/
dijkstra(gp,gm,s,n);
/*輸出結果*/
printf("%d %d\n",node[e].d, node[e].m);
/*釋放空間*/
free(gm);
free(gp);
/*等待下組數據*/
scanf("%d%d",&n,&m);
}
}
