IPSC 1999 H - Remeo

前天团队训练赛的题...
不得不吐槽老师从哪里弄到的题...拿到手里还是.webarchieve格式...折腾了一阵才打开
真羡慕那些用Mac的土豪...QwQ(留下了贫穷的泪水)

来源 IPSC 1999

1.png
2.png

题意大致如下:
罗密欧要去打篮球,朱丽叶要去教堂,他们同时从两个起点出发,向两个不同的终点前进,所走的路径都是最短路径,问是否存在某一情况,两人在一点上相遇,存在输出相遇的时间,不存在输出-1

思路:
如果存在这种情况的话,这个点一定被两人都走过,而且是两人最短路径上的公共点
看到最短路首先想到Dijkstra算法,最短路问题解决之后就是对走过的最短路打标记,之后判断被标记的点到两人起点距离是否相同即可,看到数据范围并不是很大,直接两遍Dijkstra加上BFS标记即可,BFS时从终点开始,注意入队的判断是否是最短路径,这里我用的方法是判断当前点减去下个点的路径是否和最短路径相等

Accept 2/2 C++ 3ms 3MB:

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date    2018-05-15 17:25:06
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

const int maxN = 105;
const int INF = 2333333;

struct Time {
    int pos;
    int time;
};

int disarr[maxN][maxN];
int disRomeo[maxN];
int disJuliet[maxN];
bool vis[maxN];
int n, m, sJuliet, sRemeo, eJuliet, eRemeo;

void dijkstra(int start, int dis[]) {
    int i, j, minPos, minDis;
    //Init
    for(i = 1; i <= n; i++) {
        dis[i] = disarr[start][i];
        vis[i] = false;
    }
    vis[start] = true;
    dis[start] = 0;
    //Dijkstra
    for(i = 1; i <= n; i++) {
        minDis = INF;
        for(j = 1; j <= n; j++)
            if(vis[j] == false && dis[j] < minDis) {
                minDis = dis[j];
                minPos = j;
            }
        vis[minPos] = true;
        for(j = 1; j <= n; j++)
            if(disarr[minPos][j] != INF && dis[j] > dis[minPos] + disarr[minPos][j])
                dis[j] = dis[minPos] + disarr[minPos][j];
    }
    return;
}

void BFS(int start, int dis[]) {
    Time t;
    queue<Time> que;
    int i;
    //Init
    for(i = 1; i <= n; i++)
        vis[i] = false;
    vis[start] = true;
    que.push({start, dis[start]});
    //BFS
    while(!que.empty()) {
        t = que.front();
        que.pop();
        for(i = 1; i <= n; i++)
            if(vis[i] == false && t.time - disarr[t.pos][i] == dis[i]) {
                vis[i] = true;
                que.push({i, dis[i]});
            }
    }
    //Mark
    for(i = 1; i <= n; i++)
        if(vis[i] == false)
            dis[i] = INF;
    return;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int i, j, u, v, val, ans;
    while(~scanf("%d", &n) && n != -1) {
        scanf("%d", &m);
        scanf("%d %d %d %d", &sJuliet, &eJuliet, &sRemeo, &eRemeo);
        //Init
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                if(i == j)
                    disarr[i][j] = 0;
                else
                    disarr[i][j] = INF;
        for(i = 1; i <= n; i++)
            disJuliet[i] = disRomeo[i] = INF;
        //Scan
        for(i = 1; i <= m; i++) {
            scanf("%d %d %d", &u, &v, &val);
            disarr[u][v] = val;
            disarr[v][u] = val;
        }
        //Dijkstra
        dijkstra(sJuliet, disJuliet);
        dijkstra(sRemeo, disRomeo);
        //BFS to Mark
        BFS(eJuliet, disJuliet);
        BFS(eRemeo, disRomeo);
        //Solve
        ans = INF;
        for(i = 1; i <= n; i++)
            if(disJuliet[i] == disRomeo[i])
                ans = min(ans, disJuliet[i]);
        //Output
        if(ans == INF)
            printf("-1\n");
        else
            printf("%d\n", ans );
    }
    return 0;
}

    • 2018-05-25 22:36 回复

      鱼儿加个友链怎么样?我先给你加上了

    • 2018-06-04 18:47 回复

      Emmm....
      没想到小诺诺你还活着....
      已加

添加新评论

captcha
请输入验证码