最短路算法记录最短路径

Dijkstra记录最短路径

CodeForces 20C Dijkstra?（Dijkstra记录路径）

题目点这里=V=
只要在只需要在松弛过程中记录成功松弛的点作为前驱即可

#include <bits/stdc++.h>
using namespace std;
/*    freopen("k.in", "r", stdin);
    freopen("k.out", "w", stdout); */
// clock_t c1 = clock();
// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ls ((x) << 1)
#define rs ((x) << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef vector<int, int> VII;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 2e5 + 7;
const ll MAXM = 1e6 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1.0);
struct Edge
{
    int u, v, w, net;
    Edge(int _u = 0, int _v = 0, int _w = 0, int _net = 0) { u = _u, v = _v, w = _w, net = _net; }
} E[MAXN << 2];
int cnt = -1;
int head[MAXN];
void add_edge(int u, int v, int w)
{
    E[++cnt] = Edge(u, v, w, head[u]);
    head[u] = cnt;
}
bool vis[MAXN];
ll dis[MAXN];
int pre[MAXN];
struct node
{
    int v;
    ll c;
    node(int _v = 0, ll _c = 0) { v = _v, c = _c; }
    bool operator<(const node &a) const
    {
        if (c == a.c)
            return v < a.v;
        return c > a.c;
    }
};
void Dijkstra(int n, int st)
{
    priority_queue<node> pq;
    dis[st] = 0;
    pq.push(node(st, 0));
    while (!pq.empty())
    {
        node temp = pq.top();
        pq.pop();
        int u = temp.v;
        if (vis[u])
            continue;
        vis[u] = 1;
        for (int i = head[u]; ~i; i = E[i].net)
        {
            int v = E[i].v;
            int cost = E[i].w;
            if (!vis[v] && cost + dis[u] < dis[v])
            {
                dis[v] = cost + dis[u];
                pre[v] = u;
                pq.push(node(v, dis[v]));
            }
        }
    }
}
int n, m;
void init(int n)
{
    cnt = -1;
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    for (int i = 1; i <= n; i++)
        pre[i] = -1;
}
vector<int> ans;
int main()
{
    scanf("%d%d", &n, &m);
    init(n);
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }
    Dijkstra(n, 1);
    if (dis[n] == INF)
        printf("-1
");
    else
    {
        ans.push_back(n);
        int p = pre[n];
        while (p != -1)
        {
            ans.push_back(p);
            p = pre[p];
        }
        for (int i = ans.size() - 1; i >= 0; i--)
            printf("%d%c", ans[i], " 
"[i == 0]);
    }
    return 0;
}

Floyd记录最短路径

HDU-1224 Free DIY Tour

题目链接=v=
在插点过程中记录前驱，dfs输出路径

#include <bits/stdc++.h>
using namespace std;
/*    freopen("k.in", "r", stdin);
    freopen("k.out", "w", stdout); */
// clock_t c1 = clock();
// std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define ls ((x) << 1)
#define rs ((x) << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef vector<int, int> VII;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 2e5 + 7;
const ll MAXM = 1e6 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1.0);
int dis[105][105];
int a[105];
int path[105][105];
int n, m;
void dfs(int x, int y)
{
    if (path[x][y] == -1)
        printf("%d->%d", x, y);
    else
    {
        dfs(x, path[x][y]);
        printf("->%d", y == n ? 1 : y);
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    for (int Case = 1; Case <= t; Case++)
    {
        memset(dis, inf, sizeof(dis));
        memset(path, -1, sizeof(path));
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            dis[i][i] = 0;
        }
        a[++n] = a[1];
        dis[n][n] = 0;
        scanf("%d", &m);
        while (m--)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            dis[u][v] = -a[v];
        }
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (dis[i][k] + dis[k][j] < dis[i][j])
                    {
                        dis[i][j] = dis[i][k] + dis[k][j];
                        path[i][j] = k;
                    }
        printf("CASE %d#
points : %d
", Case, -dis[1][n]);
        printf("circuit : ");
        int pre = path[1][n];
        dfs(1, n);
        printf("
");
        if (t != Case)
            printf("
");
    }
    return 0;
}