By yusijia

Updated:

Contents
  1. 1. 题目大意：
  2. 2. 分析：

题目大意：

求最短距离且最少花费，如果路线有几条，就找花费最少的。

分析：

求最短距离dis数组的时候，也把tmpcost数组给求出来，注意要加一个特判，如果路线距离相同，找花费最少的

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

//hdu3790
/*#include <cstdio>
#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 %d\n" , 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;
}
Contents
  1. 1. 题目大意：
  2. 2. 分析：