在线地图

https://www.acwing.com/problem/content/description/1603/

思路：
常见的最短路题型，只不过这题要做两次dijk。

#include<bits/stdc++.h>
using namespace std;
const int N = 550;
int g[N][N];
int cost[N][N];
int d[N];
int d2[N];
int timez[N];
int countz[N];
int pre[N];
int pre2[N];
bool st[N];
int n, m;
int start, dest;

void dijk()
{
    memset(d, 0x3f, sizeof d);
    memset(d2, 0x3f, sizeof d2);
    d2[start] = 0;
    d[start] = 0;
    countz[start] = 1;

    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 0; j <n; j++)
        {
            if (!st[j] && (t == -1 || d[t]>d[j]))
            {
                t = j;
            }
        }

        st[t] = true;

        for (int j = 0; j <n; j++)
        {
            if (d[j] > d[t] + g[t][j])
            {
                d[j] = d[t] + g[t][j];
                countz[j] =countz[t]+1;
                pre[j] = t;
                timez[j] = timez[t] + cost[t][j];
            }
            else if (d[j] == d[t] + g[t][j])
            {

                if (timez[j] > timez[t] + cost[t][j])
                {
                    timez[j] = timez[t] + cost[t][j];
                    pre[j] = t;
                    countz[j] += 1;
                }
                else if (timez[j] == timez[t] + cost[t][j])
                {
                    if (countz[j] > countz[t] + 1)
                    {
                        pre[j] = t;
                        countz[j] = countz[t] + 1;
                    }
                }
            }

        }
    }

    memset(st, false, sizeof st);
    memset(countz, 0, sizeof countz);
    countz[start] = 1;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 0; j < n; j++)
        {
            if (!st[j] && (t == -1 || d2[t]>d2[j]))
            {
                t = j;
            }
        }

        st[t] = true;

        for (int j = 0; j < n; j++)
        {
            if (d2[j] > d2[t] + cost[t][j])
            {
                d2[j] = d2[t] + cost[t][j];
                countz[j] = countz[t] + 1;
                pre2[j] = t;
            }
            else if (d2[j] == d2[t] + cost[t][j])
            {

                if (countz[j]>countz[t]+1)
                {
                    pre2[j] = t;
                    countz[j] = countz[t] + 1;
                }
            }

        }
    }
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    memset(cost, 0x3f, sizeof cost);
    for (int i = 1; i <= m; i++)
    {
        int a, b, flag, length, time;
        cin >> a >> b >> flag >> length >> time;
        if (flag == 1)
        {
            g[a][b] = min(g[a][b], length);
            cost[a][b] = min(cost[a][b], time);
        }
        else
        {
            g[a][b] = g[b][a] = min(g[a][b], length);
            cost[a][b] = cost[b][a] = min(cost[a][b],time);
        }
    }
    cin >> start >> dest;
    dijk();
    vector<int> res1, res2;
    for (int i = dest; i != start; i = pre[i]) res1.push_back(i);
    for (int i = dest; i != start; i = pre2[i]) res2.push_back(i);
    if (res1 == res2)
    {
        printf("Distance = %d; Time = %d: ", d[dest], d2[dest]);
        cout << start;
        for (int i = res1.size() - 1; i >= 0; i--)
        {
            cout << " -> " << res1[i];
        }
    }
    else
    {
        printf("Distance = %d: ", d[dest]);
        cout << start;
        for (int i = res1.size() - 1; i >= 0; i--)
        {
            cout << " -> " << res1[i];
        }
        cout << endl;
        printf("Time = %d: ",d2[dest]);
        cout << start;
        for (int i = res2.size() - 1; i >= 0; i--)
        {
            cout << " -> " << res2[i];
        }
    }
    return 0;
}