题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=103

题目大意

Dingiville 城市的交通规则非常奇怪,城市公路通过路口相连,两个不同路口之间最多只有一条直达公路。公路的起止点不会是同一路口。在任意一条公路上顺不同方向走所需 时间相同。每一个路口都有交通灯,这些交通灯在某一时刻要么是蓝色,要么是紫色。同一个灯上2个颜色的维持时间受到定期调控,总是蓝色持续一段时间,紫色 持续一段时间。交通规则规定两个路口可以通车仅当公路两边交通灯的颜色相同(也就是说只要你在A城市看见A与B的交通灯颜色相同,那么你就可以走上A-B 这条路并到达B点)。交通工具可以在路口等候。现在你有这个城市的地图,包含: 

• 通过所有公路需要的时间(整数) 

• 每个路口交通灯两种颜色的持续时间(整数) 

• 每个路口交通灯的初始颜色以及初始颜色的持续时间(整数). 

你的任务是找到一条从起点到终点的最快路径,当有多条这样的路径存在时,你只需输出任意一条即可。

题解

此题求最短路,唯一的难点在于如何计算出A到B的确切时间。

int getColor(int x, int cur, int &tim) {
    if (cur < a[x].c) {
        tim = a[x].c - cur;
        if (a[x].color == 'B') return 1;
        return 0;
    }
    int sum = a[x].b + a[x].p, tmp = cur - a[x].c;
    if (a[x].color == 'B') {
        if (tmp % sum < a[x].p) {
            tim = a[x].p - tmp % sum;
            return 0;
        }
        tim = sum - tmp % sum;
        return 1;
    }
    if (tmp % sum < a[x].b) {
        tim = a[x].b - tmp % sum;
        return 1;
    }
    tim = sum - tmp % sum;
    return 0;
}

int getLen(int cur, int u, int v, int cnt) {
    if (cnt == 3) return inf;
    int timu, timv;
    int coloru = getColor(u, cur, timu), colorv = getColor(v, cur, timv);
    if (coloru == colorv) return 0;
    if (timu == timv) return timu + getLen(cur + timu, u, v, cnt + 1);
    return min(timu, timv);
}

而此题唯一的坑点在于读入,我原来的读入代码是这样子的:

    for (int i = 1; i <= n; ++i) scanf("%c%d%d%d%*c", &a[i].color, &a[i].c, &a[i].b, &a[i].p);

上面这个代码在第15个数据Runtime Eroor,后来改成下面这样子就过了,坑爹啊!谁能告诉我为什么?!貌似不止一次遇到过这种情况,到现在为止还是不理解原因,我怀疑是数据的问题。

    for (int i = 1; i <= n; ++i) {
        char str[2];
        scanf("%s%d%d%d", str, &a[i].c, &a[i].b, &a[i].p);
        a[i].color = str[0];
    }

代码

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 300, M = 2e4, inf = 1e9;
struct adge {
    int v, len, next;
};
struct node {
    char color;
    int c, b, p;
};

int first[N + 5], dis[N + 5], pre[N + 5];
adge f[M*2 + 5];
node a[N + 5];
queue<int> Q;
bool visit[N + 5];

void addEdge(int k, int u, int v, int len) {
    f[k].v = v;
    f[k].len = len;
    f[k].next = first[u];
    first[u] = k;
    return;
}

int getColor(int x, int cur, int &tim) {
    if (cur < a[x].c) {
        tim = a[x].c - cur;
        if (a[x].color == 'B') return 1;
        return 0;
    }
    int sum = a[x].b + a[x].p, tmp = cur - a[x].c;
    if (a[x].color == 'B') {
        if (tmp % sum < a[x].p) {
            tim = a[x].p - tmp % sum;
            return 0;
        }
        tim = sum - tmp % sum;
        return 1;
    }
    if (tmp % sum < a[x].b) {
        tim = a[x].b - tmp % sum;
        return 1;
    }
    tim = sum - tmp % sum;
    return 0;
}

int getLen(int cur, int u, int v, int cnt) {
    if (cnt == 3) return inf;
    int timu, timv;
    int coloru = getColor(u, cur, timu), colorv = getColor(v, cur, timv);
    if (coloru == colorv) return 0;
    if (timu == timv) return timu + getLen(cur + timu, u, v, cnt + 1);
    return min(timu, timv);
}

void printPath(int x) {
    if (pre[x]) printPath(pre[x]);
    printf("%d ", x);
    return;
}

void solve(int s, int t, int n) {
    while (!Q.empty()) Q.pop();
    for (int i = 1; i <= n; ++i) pre[i] = 0;
    for (int i = 1; i <= n; ++i) visit[i] = false;
    visit[s] = true;
    for (int i = 1; i <= n; ++i) dis[i] = inf;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
        int u = Q.front();
        visit[u] = false;
        Q.pop();
        for (int i = first[u]; i; i = f[i].next) {
            int v = f[i].v, len = f[i].len + getLen(dis[u], u, v, 0);
            if (dis[u] + len < dis[v]) {
                dis[v] = dis[u] + len;
                pre[v] = u;
                if (!visit[v]) {
                    visit[v] = true;
                    Q.push(v);
                }
            }
        }
    }
    if (pre[t] == 0) printf("0\n");
    else {
        printf("%d\n", dis[t]);
        printPath(pre[t]);
        printf("%d\n", t);
    }
    return;
}

int main() {
    int s, t;
    scanf("%d%d", &s, &t);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        char str[2];
        scanf("%s%d%d%d", str, &a[i].c, &a[i].b, &a[i].p);
        a[i].color = str[0];
    }
    for (int i = 1; i <= n; ++i) first[i] = 0;
    for (int i = 1; i <= m; ++i) {
        int u, v, len;
        scanf("%d%d%d", &u, &v, &len);
        addEdge(i*2 - 1, u, v, len);
        addEdge(i*2, v, u, len);
    }
    if (s == t) printf("0\n%d\n", s);
    else solve(s, t, n);
    return 0;
}
转载保留版权:http://haipz.com/blog/i/6434 - 海胖博客