avatar
fireworks99
keep hungry keep foolish

最短路记录路径 POJ 2457

Description

m条单向路，n个点（1~n）

求从1到n的最短路，不存在输出“-1”，存在则输出路径

点我飞过去

Floyd

较为特殊，数组pre[i][j]存从i到j的最短路径上i后面的第一个点

当然对于此题Floyd已超时了，但算法是对的

Code of Floyd

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;


int m, n;
int mp[1005][1005];
int pre[1005][1005];
///pre[i][j]存从i到j的最短路径上i后面的第一个点

void init()
{
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
        {
            mp[i][j] = (i == j ? 0: INF);
            pre[i][j] = j;
        }
}

void floyd()
{
    vector<int> ans;
    for(int k = 1; k <= n; ++k)///我无语了，又写成了++i
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                if(mp[i][j] > mp[i][k] + mp[k][j])
                {
                    mp[i][j] = mp[i][k] + mp[k][j];
                    pre[i][j] = pre[i][k];
                }
    if(mp[1][n] == INF)
        cout << "-1" << '\n';
    else
    {
        vector<int> ans;
        ans.push_back(1);
        int pos = pre[1][n];
        while(pos != n)
        {
            ans.push_back(pos);
            pos = pre[pos][n];
        }
        ans.push_back(n);
        int sz = ans.size();
        cout << sz << '\n';
        for(int i = 0; i < sz; ++i)
            cout << ans[i] << '\n';
    }
    return ;
}

int main()
{
    while(~scanf("%d%d", &m, &n))
    {
        init();
        int there, here;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &there, &here);
            mp[there][here] = 1;
        }
        floyd();
    }
    return 0;
}

Dijkstra

nodepre[N]，这种最短路的记录路径，就像BFS的记录路径pre，像最长递增子序列的记录路径pre，像链式前向星的pre。

Code of Dijkstra

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;

int m, n;
bool vis[1005];
int head[1005], dis[1005];
int nodepre[1005];
///路径都是pre存(由后推前)，而非nxt(由前推后)的原因：
///更新方向：由前向后，一点更新多点
///即：一点有多个nxt,却只有一个"有实际意义的"pre

int cnt;
struct edge
{
    int from, to, w, pre;
} a[50005];

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
}

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
    {
        dis[i] = INF;
        vis[i] = 0;
        head[i] = -1;
        nodepre[i] = -1;
    }
}

void Dijkstra(int start)
{
    dis[start] = 0;
    int pos = start;
    int mmin;
    while(pos != -1)
    {
        for(int i = head[pos]; ~i; i = a[i].pre)
        {
            if(vis[ a[i].to ])
                continue;
            if(dis[ a[i].to ] == INF || dis[ a[i].to ] > dis[pos] + a[i].w)
            {
                dis[ a[i].to ] = dis[pos] + a[i].w;
                nodepre[ a[i].to ] = pos;
            }
        }
        vis[pos] = 1;

        pos = -1;
        mmin = -1;
        for(int i = 1; i <= n; ++i)
            if(!vis[i] && dis[i] != INF && (mmin == -1 || mmin > dis[i]))
            {
                mmin = dis[i];
                pos = i;
            }
    }
    if(dis[n] == INF)
    {
        cout << "-1" << '\n';
        return ;
    }
    vector<int> ans;
    pos = n;
    while(nodepre[pos] != -1)
    {
        ans.push_back(pos);
        pos = nodepre[pos];
    }
    ans.push_back(start);
    int sz = ans.size();
    cout << sz << '\n';
    for(int i = sz - 1; i >= 0; --i)
        cout << ans[i] << '\n';
    return ;
}

int main()
{
    while(~scanf("%d%d", &m, &n))
    {
        init();
        int there, here;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &there, &here);
            add(there, here, 1);
        }
        Dijkstra(1);
    }
    return 0;
}

Bellman_Ford

同Dijkstra普通记录路径方法

Code of Bellman_Ford

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int m, n, dis[1005], nodepre[1005];

int cnt;
struct edge
{
    int from, to, w;
} a[50005];

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    cnt++;
}

bool Bellman_Ford(int start)
{
    dis[start] = 0;

    int tot = n;
    while(tot--)
    {
        bool flag = 0;
        for(int i = 0; i < cnt; ++i)
            if(dis[ a[i].to ] > dis[ a[i].from ] + a[i].w)
            {
                flag = 1;
                dis[ a[i].to ] = dis[ a[i].from ] + a[i].w;
                nodepre[ a[i].to ] = a[i].from;
            }
        if(!flag)
            break;
    }
    for(int i = 0; i < cnt; ++i)
        if(dis[ a[i].to ] > dis[ a[i].from ] + a[i].w)
            return 0;
    if(dis[n] == INF)
        cout << "-1" << '\n';
    else
    {
        int pos = n;
        vector<int> ans;
        while(pos != -1)
        {
            ans.push_back(pos);
            pos = nodepre[pos];
        }
        int sz = ans.size();
        cout << sz << '\n';
        for(int i = sz - 1; i >= 0; --i)
            cout << ans[i] << '\n';
    }
    return 1;
}

int main()
{
    while(~scanf("%d%d", &m, &n))
    {
        cnt = 0;
        memset(dis, INF, sizeof(dis));
        memset(nodepre, -1, sizeof(nodepre));
        int there, here;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &there, &here);
            add(there, here, 1);
        }
        if(Bellman_Ford(1))
            continue;
    }
    return 0;
}

spfa

同Dijkstra普通记录路径方法

Code of spfa

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int m, n;
bool vis[1005];
int head[1005], dis[1005], times[1005], tot, sum;
int nodepre[1005];

int cnt;
struct edge
{
    int from, to, w, pre;
} a[50005];

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cnt++;
}

void init()
{
    cnt = 0;
    for(int i = 0; i <= n; ++i)
    {
        dis[i] = INF;
        vis[i] = 0;
        times[i] = 0;
        head[i] = -1;
        nodepre[i] = -1;
    }
}

bool spfa(int start)
{
    dis[start] = 0;
    deque<int> q;
    q.push_front(start);
    vis[start] = 1;
    tot = 1, sum = 0;

    while(q.size())
    {
        int first = q.front();
        q.pop_front();
        vis[first] = 0;
        sum -= dis[first];
        tot--;

        for(int i = head[first]; ~i; i = a[i].pre)
        {
            int t = a[i].to;
            if(dis[t] > dis[first] + a[i].w)
            {
                dis[t] = dis[first] + a[i].w;
                nodepre[t] = first;
                if(!vis[t])
                {
                    vis[t] = 1;
                    if(q.empty() || dis[q.front()] < dis[t] || dis[t] * tot >= sum)
                        q.push_back(t);
                    else
                        q.push_front(t);
                    sum += dis[t];
                    tot++;
                    if(++times[t] >= n)
                        return 0;
                }
            }
        }
    }
    if(dis[n] == INF)
        cout << "-1" << '\n';
    else
    {
        int pos = n;
        vector<int> ans;
        while(pos != -1)
        {
            ans.push_back(pos);
            pos = nodepre[pos];
        }
        int sz = ans.size();
        cout << sz << '\n';
        for(int i = sz - 1; i >= 0; --i)
            cout << ans[i] << '\n';
    }
    return 1;
}

int main()
{
    while(~scanf("%d%d", &m, &n))
    {
        init();
        int there, here;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d", &there, &here);
            add(there, here, 1);
        }
        if(spfa(1))
            continue;
    }
    return 0;
}
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy