1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#include <iostream>
#include <cstring>
#define MAXN 1000
#define INF 0x3f3f3f3f //INF一般设成这个，
//防止dis[MinNumber] + mp[MinNumber][j]溢出
using namespace std;
int cost[MAXN][MAXN];
int tmpcost[MAXN];
int value[MAXN][MAXN];
int dis[MAXN];
int n, m, begins, End;
int vis[MAXN];
void init()
{
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
value[i][j] = INF;
cost[i][j] = INF;
}
}
}
void solve(int start)
{
memset(dis, INF, sizeof(dis));
memset(vis, 0, sizeof(vis));
memset(tmpcost, INF, sizeof(tmpcost));
dis[start] = tmpcost[start] = 0;
for(int i = 1; i <= n; i++){
int Min = INF, MinNumber;
for(int j = 1; j <= n; j++) if(dis[j] < Min && !vis[j]){
Min = dis[j];
MinNumber = j;
}
vis[MinNumber] = 1;
for(int j = 1; j <= n; j++){
if(dis[j] > dis[MinNumber] + value[MinNumber][j]){
dis[j] = dis[MinNumber] + value[MinNumber][j];
tmpcost[j] = tmpcost[MinNumber] + cost[MinNumber][j];
}
else if(dis[j] == dis[MinNumber] + value[MinNumber][j]){
if(tmpcost[j] > tmpcost[MinNumber] + cost[MinNumber][j])
tmpcost[j] = tmpcost[MinNumber] + cost[MinNumber][j];
}
}
}
printf("%d %dn" , dis[End] , tmpcost[End]);
}
int main()
{
int a, b, v, c;
while(scanf("%d%d", &n, &m) != EOF && n + m){
init();
for(int i = 0; i < m; i++){
scanf("%d%d%d%d", &a, &b, &v, &c);
if(value[a][b] > v){
value[a][b] = value[b][a] = v;
cost[a][b] = cost[b][a] = c;
}
else if(value[a][b] == v && cost[a][b] > c){
cost[a][b] = cost[b][a] = c;
}
}
scanf("%d%d", &begins, &End);
solve(begins);
}
return 0;
}
|
近期评论