1111 Online Map（30 分）

这个题感觉考得是手速emmm，常规题目，不难
(半个小时手没停emmm)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 1e9 + 10;
const int maxn = 510;
int G[maxn][maxn], d[maxn], T[maxn][maxn], t[maxn];
bool vis[maxn];
int source, des;
int n, m;
int pre[maxn];
vector<int>dpath, tpath;
void Dijkstra(int s)
{
    fill(d, d + maxn, INF);
    d[s] = 0;
    fill(t, t + maxn, INF);
    t[s] = 0;
    while (1)
    {
        int u = -1, MIN = INF;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i] && d[i] < MIN)MIN = d[i], u = i;
        }
        if (u == -1)break;
        vis[u] = true;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i] && G[u][i])
            {
                if (d[u] + G[u][i] < d[i])
                {
                    d[i] = d[u] + G[u][i];
                    t[i] = t[u] + T[u][i];
                    pre[i] = u;
                }
                else if (d[u] + G[u][i] == d[i] & t[u] + T[u][i] < t[i])
                {
                    pre[i] = u;
                }
            }
        }
    }
}
void DFS(int v)
{
    if (v == source)
    {
        dpath.push_back(source);
        return;
    }
    DFS(pre[v]);
    dpath.push_back(v);
}

int pret[maxn], pt[maxn];
void DijkstraT(int s)
{
    memset(vis, false, sizeof(vis));
    fill(t, t + maxn, INF);
    t[s] = 0;
    pt[s] = 1;
    while (1)
    {
        int u = -1, MIN = INF;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i] && t[i] < MIN)MIN = t[i], u = i;
        }
        if (u == -1)break;
        vis[u] = true;
        for (int i = 0; i < n; i++)
        {
            if (!vis[i] && T[u][i])
            {
                if (t[u] + T[u][i] < t[i])
                {
                    t[i] = t[u] + T[u][i];
                    pret[i] = u;
                    pt[i] = pt[u] + 1;
                }
                else
                {
                    if (t[u] + T[u][i] == t[i] && pt[u] + 1 < pt[i])
                    {
                        pret[i] = u;
                        pt[i] = pt[u] + 1;
                    }
                }
            }
        }
    }
}
void DFST(int v)
{
    if (v == source)
    {
        tpath.push_back(v);
        return;
    }
    DFST(pret[v]);
    tpath.push_back(v);
}
int caldis()
{
    int ans = 0;
    for (int i = 0; i < dpath.size()-1; i++)
    {
        int v = dpath[i], u = dpath[i + 1];
        ans += G[v][u];
    }
    return ans;
}
int caltime()
{
    int ans = 0;
    for (int i = 0; i < tpath.size()-1; i++)
    {
        int v = tpath[i], u = tpath[i + 1];
        ans += T[v][u];
    }
    return ans;
}
void show(vector<int>path)
{
    for (int i = 0; i < path.size(); i++)
    {
        printf(" %d", path[i]);
        if (i != path.size() - 1)printf(" ->");
    }
    printf("\n");
}
int main()
{
    scanf("%d%d", &n, &m);
    while (m--)
    {
        int v1, v2, ow, length, time;
        scanf("%d%d%d%d%d", &v1, &v2, &ow, &length, &time);
        if (ow == 0)
        {
            G[v1][v2] = G[v2][v1] = length;
            T[v1][v2] = T[v2][v1] = time;
        }
        else
        {
            G[v1][v2] = length;
            T[v1][v2] = time;
        }
    }
    scanf("%d%d", &source, &des);
    Dijkstra(source);
    DFS(des);
    DijkstraT(source);
    DFST(des);
    int dis = caldis(), tottime = caltime();
    bool f = true;
    for (int i = 0; i < min(dpath.size(), tpath.size()); i++)
    {
        if (dpath[i] != tpath[i])
        {
            f = false;
            break;
        }
    }
    if (f == false)
    {
        printf("Distance = %d:", dis);
        show(dpath);
        printf("Time = %d:", tottime);
        show(tpath);
    }
    else
    {
        printf("Distance = %d;", dis);
        printf(" Time = %d:", tottime);
        show(tpath);
    }
    return 0;
}