最短路

POJ 2449 Remmarguts’ Date

Posted on

K短路裸题。

这里的K短路是基于每个点只能访问一次,也就是说这个K短路必须是一条链。
再换句话说,这个K短路的K是有限制的,如果超过了这个限制,就输出 -1 。
这是和之前多校的次短路不一样的地方。

简单说一下K短路的解决思路:
首先我们应该认识到,最最简单的最短路算法是基于 bfs 改进而来,我们用 bfs 的思路继续拓展,在第一次到达终点后并不停止,而是继续 bfs 搜索,直到第K次到达终点,就是我们要求的答案。
当然,单纯的 bfs 是瞎 jb 搜,堆优化的spfa效率良好,但我们可以更进一步优化。
K短路于此之上还用了 A* 优化,先对反图 最短路遍历一遍,在正图遍历的时候,除了对起点 src 到当前距离 堆优化以外,还对当前距离进行答案估计,并将其优先级先于距离。

仔细想一想,其实很显然,不过为什么最短路不用 A* 优化呢?
因为有处理估值函数的时间,最短路都已经求完了。

题意:
K短路裸题。

思路:
见上。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int maxm = 1e5 + 5;

int idx, n, m;
int src, des;
int head[maxn], head2[maxn];
bool inq[maxn];
int dis[maxn];

struct node {
    int to, weight;
    int next;
    node(int a = 0, int b = 0, int c = 0) { to = a, weight = b, next = c; }
    bool operator<(const node& a) const { return weight > a.weight; }
} edges[maxm], redges[maxm];

struct qnode {
    int node, dist, src_dis;
    bool operator<(const qnode& a) const { return dist == a.dist ? src_dis > a.src_dis : dist > a.dist; }
} tmp;

void addEdge(int u, int v, int w)
{
    edges[idx] = node(v, w, head[u]);
    head[u] = idx;
    redges[idx] = node(u, w, head2[v]);
    head2[v] = idx++;
}

void spfa(int st)
{
    queue<int> que;
    fill(dis, dis + 1 + n, inf);
    dis[st] = 0, inq[st] = true;
    que.push(st);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        inq[u] = false;
        for (int id = head2[u]; ~id; id = redges[id].next) {
            int v = redges[id].to;
            if (dis[v] > dis[u] + redges[id].weight) {
                dis[v] = dis[u] + redges[id].weight;
                if (!inq[v]) {
                    inq[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

void nthSP(int k)
{
    if (src == des)
        k++;
    priority_queue<qnode> que;
    que.push((qnode){ src, 0, 0 });
    int cnt = 0;
    while (!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.node, dist = tmp.src_dis;
        if (u == des) {
            if (++cnt == k) {
                printf("%d\n", tmp.dist);
                return;
            }
        }
        for (int id = head[u]; ~id; id = edges[id].next)
            que.push((qnode){ edges[id].to, dist + edges[id].weight + dis[edges[id].to], dist + edges[id].weight });
    }
    puts("-1");
}

int main()
{
    int u, v, w, k;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(head, -1, sizeof head), idx = 0;
        memset(head2, -1, sizeof head2);
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
        }
        scanf("%d %d %d", &src, &des, &k);
        spfa(des);
        nthSP(k);
    }
    return 0;
}
最短路

HDU 1599 find the mincost route

Posted on

昨天晚上从Yasola那里偷来的一道题……

为什么Yasola这么优秀啊!!!!!
求求你别学了,我已经完全跟不上了……

因为看着题目并不是很难我也就写了一蛤,然后自以为是无脑题就疯狂WA……

emmmm…… 其实仔细想想还是挺简单的。

题意:
给你一张无向图,要你找出最小环。

点数 \( n \leq 100 \)

思路:
对 floyd 进行简单增加一点代码。
floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前,将其固定为环上的一个点,这点必定不会被所有最短路夹在中间。


有一个非常显然的问题就是,当我固定一个中间结点的时候,我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。

比如说
存在一个 ABCA 的环与一个 BCDB,其中 \( BD + DC < BC , AB + AC < BC \),而当我使 A 为固定结点,而我的 D 还不曾成为固定结点,也就不会被加入 BC 的最短路。

然而实际上并不要担心,这个环仍然会在floyd后期进行更新,因为对一个环来说,总存在最后一个被作为固定结点。
假设最糟糕的情况,D 结点是 ABCD 结点中最后一个被作为固定结点,那么不也能成功加入 BAC这条最短路径么。

AC Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int inf = 1e8;
const int maxn = 105;

int G[maxn][maxn];
int dis[maxn][maxn];

int main()
{
    int n, m, u, v, w;
    while (scanf("%d %d", &n, &m) != EOF) {
        range(i, 1, n) range(j, 1, n) G[i][j] = i == j ? 0 : inf;
        while (m--) {
            scanf("%d %d %d", &u, &v, &w);
            G[u][v] = G[v][u] = min(G[u][v], w);
        }
        range(i, 1, n) range(j, 1, n) dis[i][j] = G[i][j];
        int ans = inf;
        range(k, 1, n)
        {
            range(i, 1, k - 1) range(j, i + 1, k - 1) ans = min(ans, dis[i][j] + G[i][k] + G[k][j]);
            range(i, 1, n) range(j, 1, n) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
        ans == inf ? printf("It's impossible.\n") : printf("%d\n", ans);
    }
    return 0;
}
最短路

HDU 4725 The Shortest Path in Nya Graph

Posted on

貌似是卡spfa的,但薛昊说slf优化一下也可以过
个人感觉写的非常崩溃……用数组实现队列的时候是WA,stl实现就是tle,我觉得这很可能是空间上的问题。因为最近数组大小开错不停wa不停tle的情况太多了……
看很多题解都是dijkstra实现的。改了一下直接A了

题意:
美团初赛城市群的原题……上次没写出来,碰到原题真的是内心崩溃。
简单说,在一张图的基础上,每个节点都会属于一个 “ 层 ” ,每个相邻的 “ 层 ” 中的节点都相互可达,问 1 到 n 的最短距离。

思路:
对 “ 层 ” 建立源点与汇点,对于每个层里面的每个点,源点到点 ,点到汇点的距离各为 0 。再对 “ 层 ” 之间建边,点之间建边跑最短路即可。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;

int dis[maxn], head[maxn];
bool vis[maxn];
int n, m, c, idx;

struct node {
    int to;
    int nxt;
    int weight;
} edges[maxn];

struct qnode {
    int to;
    int weight;
    qnode(int _to = 0, int _weight = 0)
        : to(_to)
        , weight(_weight)
    {
    }
    bool operator<(const qnode& a) const
    {
        return weight > a.weight;
    }
};

priority_queue<qnode> que;

void Dijkstra(int n, int start) 
{
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <=3* n; i++)
        dis[i] = inf;
    while (!que.empty())
        que.pop();
    dis[start] = 0;
    que.push(qnode(start, 0));
    qnode tmp;
    while (!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.to;
        if (vis[u])
            continue;
        vis[u] = true;
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            int cost = edges[id].weight;
            if (!vis[v] && dis[v] > dis[u] + cost) {
                dis[v] = dis[u] + cost;
                que.push(qnode(v, dis[v]));
            }
        }
    }
    printf("%d\n", dis[n] == inf ? -1 : dis[n]);
}

inline void addEdge(int u, int v, int w)
{
    edges[idx].to = v;
    edges[idx].weight = w;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

int main()
{
    int T, u, v, w, layer;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d %d", &n, &m, &c);
        memset(head, -1, sizeof head);
        idx = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &layer);
            addEdge(n + layer * 2 - 1, i, 0);
            addEdge(i, n + 2 * layer, 0);
        }
        for (int i = 1; i < n; i++) {
            addEdge(n + 2 * i, n + 2 * i + 1, c);
            addEdge(n + 2 * i + 2, n + 2 * i - 1, c);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &w);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }
        printf("Case #%d: ", cas);
        Dijkstra(n,1);
    }
    return 0;
}
最短路

POJ 1135 Domino Effect

Posted on

这是一道多米诺骨牌的题目 从第一块骨牌出发 问最后一块倒下的骨牌在哪 若是端点 直接输出时间和端点 否则输出时间和 最后的骨牌在哪两块之间

怎么说呢 直接用spfa 算出 从1节点到其他节点的单源最短路径 找出最大的
因为作为最短路的最大值 它必定是一条路径 就算有其他的路径到达这个节点 那也是肯定逼这条最短路径要慢的
所以我们从这个最大节点出发 除了最短路径的其他路径都会是没有走过的路径(也就是还能继续走下去
详见注释

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int maxn=505;
const int inf=0x3f3f3f3f;
int n,m,idx;
int head[maxn],d[maxn];
bool vis[maxn];
struct edge
{
    int v,val;
    int nxt;
}edges[maxn*maxn];

void init()//初始化
{
    memset(head,-1,sizeof head);
    memset(vis,false,sizeof vis);
    memset(d,0x3f,sizeof d);
    idx=0;
}

void add(int u,int v,int val)//邻接表存储
{
    edges[idx].v=v;
    edges[idx].val=val;
    edges[idx].nxt=head[u];
    head[u]=idx++;

    edges[idx].v=u;
    edges[idx].val=val;
    edges[idx].nxt=head[v];
    head[v]=idx++;
}

void spfa()//spfa算法   都是套路
{
    queue<int> que;
    que.push(1);
    vis[1]=true;
    d[1]=0;
    while(!que.empty())
    {
        int tmp=que.front();
        que.pop();
        vis[tmp]=false;
        for(int u=head[tmp];u!=-1;u=edges[u].nxt)
        {
            int v=edges[u].v;
            if(d[tmp]+edges[u].val<d[v])
            {
                d[v]=d[tmp]+edges[u].val;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                }
            }
        }
    }
}

int main()
{
    int u,v,cost,test=0;
    while(scanf("%d %d",&n,&m),n||m)
    {
        init();
        while(m--)
        {
            scanf("%d %d %d",&u,&v,&cost);
            add(u,v,cost);
        }
        spfa();
        double tim=0.0;//初始化为0.0  避免考虑只有一个多米诺骨牌的情况
        int domino=1;
        for(int i=2;i<=n;i++)
        {
            if(tim<d[i])//找到最大的最短路径   并记录
            {
                tim=(double)d[i];
                domino=i;
            }
        }
        int le=domino;
        double tt=tim;
        bool flag=true;
        for(u=head[domino];u!=-1;u=edges[u].nxt)//从该节点出发
        {
            if(d[u]+edges[u].val!=d[domino])//如果不是最短路径
            {
                v=edges[u].v;
                double tmp=(double)(edges[u].val-(d[domino]-d[v]))/2.0;//计算这条路径上还能走多久
                if(tt<tmp+tim)
                {
                    tt=tim+tmp;
                    le=v;
                    flag=false;
                }
            }
        }
        if(le>domino) swap(le,domino);
        printf("System #%d\n",++test);
        if(flag) printf("The last domino falls after %.1lf seconds, at key domino %d.\n\n",tim,domino);
        else printf("The last domino falls after %.1lf seconds, between key dominoes %d and %d.\n\n",tt,le,domino);
    }
    return 0;
}