旅游规划

dijkstra

题目

Description

2000MS/65536K
有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

Input

输入说明：输入数据的第1行给出4个正整数NN、MM、SS、DD，其中NN（2\le N\le 5002≤N≤500）是城市的个数，顺便假设城市的编号为0~(N-1N−1)；MM是高速公路的条数；SS是出发地的城市编号；DD是目的地的城市编号。随后的MM行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

Output

　在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

Simple input

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

Simple output

3 40

题目分析

dijkstra的拓展，特判当距离相同的时候，dm[j]取dm[j]和mo[u][j]+dm[u]中的最小值

AC代码

7996K/31MS

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
void fre()
{
    freopen("c://test//input.in", "r", stdin);
    freopen("c://test//output.out", "w", stdout);
}
#define MP(x,y) make_pair(x,y)
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
#define debug puts("----------")
#define inf 0x3f3f
#define maxn 1050
const long long mod = 1e9+7;
using namespace std;
typedef int mytype;
const int NV=1005;
typedef int mytype;
int pre[NV],vis[NV];
mytype dis[NV],g[NV][NV];
mytype dm[NV],mo[NV][NV];
int v[NV][NV];
void init(int n,int m,int s)
{
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
    for (int i=0; i<=n; i++)
    {
        dm[i]=inf;
        dis[i]=inf;
    }
    dis[s]=0;
    dm[s]=0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
        {
            mo[i][j]=inf;
            g[i][j]=inf;
        }
    for (int i=1; i<=m; i++)
    {
        int u,v,l,tem;
        scanf("%d%d%d%d",&u,&v,&l,&tem);
        g[u+1][v+1]=l;
        g[v+1][u+1]=l;
        mo[u+1][v+1]=tem;
        mo[v+1][u+1]=tem;
    }
}
void dijkstra(int n)
{
    for (int i=1; i<=n; i++)
    {
        memset(v,0,sizeof(vis));
        int u=0;
        for (int j=1; j<=n; j++)
            if (!vis[j]&&dis[j]<dis[u])
                u=j;
        vis[u]=1;
        for (int j=1; j<=n; j++)
        {
            if (dis[u]+g[u][j]<dis[j])
            {
                dis[j]=dis[u]+g[u][j];
                dm[j]=dm[u]+mo[u][j];
                pre[j]=u;
            }
            else if(g[u][j]!=inf&&!vis[j]&&dis[j] == dis[u] + g[u][j])
            {
                dm[j]=min(dm[j],dm[u]+mo[u][j]);
            }
        }
    }
}
int main()
{
    int n,m,s,d;
    scanf("%d%d%d%d",&n,&m,&s,&d);
    init(n,m,s+1);
    dijkstra(n);
    printf("%d %d\n",dis[d+1],dm[d+1]);
}