首页 > 代码库 > sgu 103 Traffic Lights

sgu 103 Traffic Lights

2024-07-04 17:13:36   228人阅读

    这道题难得不是算法，而是处理。

    题意就是让你求最短路，只有当两个点在某一秒颜色相同时，这条边才可以通行，输入首先给你 起点和终点， 然后给你 点数和边数， 接下来 n 行 初始颜色，初始颜色持续时间，蓝色持续时间，紫色持续时间。 再接下来m行，无向边的起点和终点以及通过所需的时间。

    题意他说的有些模糊，样例我看了很多遍也不对，后来才发现如果你在某一秒到达一个点，这一秒颜色和下一个点相同，但是下一秒这个点就要变色，那么是不能在这一秒走的，这个具体处理起来很麻烦

这篇博客说的很详细，戳链接：http://www.cnblogs.com/Rinyo/archive/2012/11/29/2795030.html

上代码……

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#define N 350
#define M 15000*2
#define inf 1<<30
using namespace std;

int n, m, S, T;
int p[N] = {0}, next[M], v[M], bnum = 0, c[M], fa[N];
int dis[N], vis[N], firstcolor[N], firstremain[N], remain[N][2];

void addbian(int x, int y, int z)
{
    bnum++; next[bnum] = p[x]; p[x] = bnum;
    v[bnum] = y; c[bnum] = z;
    bnum++; next[bnum] = p[y]; p[y] = bnum;
    v[bnum] = x; c[bnum] = z;
}

void calt(int now, int nowtime, int &color, int &changetime)
{
    if (nowtime < firstremain[now])
    {
        color = firstcolor[now];
        changetime = firstremain[now];
        return;
    }
    int k;
    k = (nowtime-firstremain[now]) % (remain[now][0]+remain[now][1]);
    nowtime -= k;
    if (firstcolor[now])
    {
        if (k < remain[now][0]) { color = 0; changetime = nowtime + remain[now][0]; }
        else { color = 1; changetime = nowtime + remain[now][1] + remain[now][0]; }
    }
    else
    {
        if (k < remain[now][1]) { color = 1; changetime = nowtime + remain[now][1]; }
        else { color = 0; changetime = nowtime + remain[now][0] + remain[now][1]; }
    }
}

int gettime(int x, int y, int nowtime, int dis, int f)
{
    int ca, cb, ta, tb, ta1, ca1;
    calt(x, nowtime, ca, ta);
    calt(y, nowtime, cb, tb);
    if (ca == cb) return nowtime + dis;
    if (ta == tb)
    {
        if (f == 0) return gettime(x, y, ta, dis, f+1);
        else if (nowtime <= firstremain[x] || nowtime <= firstremain[y])
            gettime(x, y, ta, dis, f+1);
        else return inf;
    }
    return min(ta, tb) + dis;
}

void spfa()
{
    queue<int> q;
    for (int i = 1; i <= n; ++i) { vis[i] = 0; dis[i] = inf; }
    q.push(S); dis[S] = 0; vis[S] = 1;
    while (!q.empty())
    {
        int now = q.front(); q.pop();
        int k = p[now];
        while (k != 0)
        {
            int t = gettime(now, v[k], dis[now], c[k], 0);
            if (dis[v[k]] > t)
            {
                dis[v[k]] = t; fa[v[k]] = now;
                if (!vis[v[k]])
                {
                    vis[v[k]] = 1;
                    q.push(v[k]);
                }
            }
            k = next[k];
        }
        vis[now] = 0;
    }
}

void print(int now)
{
    if (now == S) printf("%d ", S);
    else
    {
        print(fa[now]);
        if (now != T) printf("%d ", now);
        else printf("%d\n", T);
    }
}

int main()
{
    scanf("%d%d", &S, &T);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        char s[2];
        scanf("%s", s);
        if (s[0] == ‘B‘) firstcolor[i] = 0;
        else firstcolor[i] = 1;
        scanf("%d%d%d", &firstremain[i], &remain[i][0], &remain[i][1]);
    }
    for (int i = 1; i <= m; ++i)
    {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        addbian(x, y, z);
    }
    spfa();
    if (dis[T] == inf)
    {
        printf("0\n");
        return 0;
    }
    printf("%d\n", dis[T]);
    print(T);
}

 


联系
我们