[codevs2070]爱情之路

试题描述

yh非常想念他的女朋友小y，于是他决定前往小y所在的那块大陆。

小y所在的大陆共有n个城市，m条双向路，每条路连接一个或两个城市。经过一条路ei需要耗费时间ti。此外，每条路均有一个特定标识，为’L’,’O’,’V’,’E’，中的某个字母。yh从1号城市出发，前往位于n号城市的小y所在处。

为了考验yh，小y规定，yh必须按照‘L’->’O’->’V’->’E’->’L’->’O’->’V’->’E’->.... 的顺序选择路，且所走的第一条路是’L’,最后一条路是’E’，每走完一个完整的’LOVE’算是通过一次考验

在不违背小y要求的前提下，yh想花费最少的时间到达小y的所在地，同在此时间内完成最多次考验。你能帮yh算出，他最少要花多久到达城市n，完成多少次考验呢？

输入

第一行为两个整数n，m表示有n个城市，m条双向路。

第2行到第m+1行，每行有3个整数x，y，t和一个字符char，城市x,y之间有路，通过这条路花费的时间为t，这条路的特殊标志为 char。

输出

输出1行，两个整数表示yh到达城市n花费的最少时间和该时间内通过的最多次考验数，如果不能到达则输出’HOLY SHIT!’

输入示例

输出示例

数据规模及约定

对于100%数据，1≤n≤1314，0≤M≤13520

题解

设置状态为 (u, t) 表示当前所在节点 u，并且刚刚经过种类为 t 的边，跑最短路。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <queue>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 1324

#define maxm 27050

#define oo (1ll << 60)

#define LL long long

int n, m, head[maxn], next[maxm], to[maxm], dist[maxm], type[maxm];

void AddEdge(int a, int b, int c, int d) {

	to[++m] = b; dist[m] = c; type[m] = d; next[m] = head[a]; head[a] = m;

	swap(a, b);

	to[++m] = b; dist[m] = c; type[m] = d; next[m] = head[a]; head[a] = m;

	return ;

}

LL d[5][maxn];

int t[5][maxn];

bool vis[5][maxn];

struct Node {

	int u, tp, t;

	LL d;

	Node() {}

	Node(int _1, LL _2, int _3, int _4): u(_1), d(_2), tp(_3), t(_4) {}

	bool operator < (const Node& T) const { return d != T.d ? d > T.d : t < T.t; }

} ;

priority_queue <Node> Q;

void Dijkstra(int s) {

	for(int j = 0; j < 4; j++)

		for(int i = 1; i <= n; i++) d[j][i] = oo;

	d[4][s] = 0; Q.push(Node(s, 0, 4, 0));

	while(!Q.empty()) {

		Node u = Q.top(); Q.pop();

		if(vis[u.tp][u.u]) continue;

		vis[u.tp][u.u] = 1;

//		printf("tp: %d, u: %d %lld\n", u.tp, u.u, d[u.tp][u.u]);

		for(int e = head[u.u]; e; e = next[e]) if((u.tp < 4 && (u.tp + 1) % 4 == type[e]) || (u.tp == 4 && !type[e])) {

			if(d[type[e]][to[e]] > d[u.tp][u.u] + dist[e]) {

				d[type[e]][to[e]] = d[u.tp][u.u] + dist[e];

				t[type[e]][to[e]] = t[u.tp][u.u] + (type[e] == 3);

				if(!vis[type[e]][to[e]]) Q.push(Node(to[e], d[type[e]][to[e]], type[e], t[type[e]][to[e]]));

			}

			else if(d[type[e]][to[e]] == d[u.tp][u.u] + dist[e] && t[type[e]][to[e]] < t[u.tp][u.u] + (type[e] == 3)) {

				t[type[e]][to[e]] = t[u.tp][u.u] + (type[e] == 3);

				if(!vis[type[e]][to[e]]) Q.push(Node(to[e], d[type[e]][to[e]], type[e], t[type[e]][to[e]]));

			}

		}

	}

	return ;

}

int main() {

	n = read(); int m = read();

	for(int i = 1; i <= m; i++) {

		int a = read(), b = read(), c = read(), d;

		char tp[2]; scanf("%s", tp);

		if(tp[0] == 'L') d = 0;

		if(tp[0] == 'O') d = 1;

		if(tp[0] == 'V') d = 2;

		if(tp[0] == 'E') d = 3;

		AddEdge(a, b, c, d);

	}

	Dijkstra(1);

	if(vis[3][n]) printf("%lld %d\n", d[3][n], t[3][n]);

	else puts("HOLY SHIT!");

	return 0;

}

数据有点坑，比如说整张图只有一个点的智障问题。

秒客网

[codevs2070]爱情之路

相关文章