首页 > 代码库 > [codevs2070]爱情之路
[codevs2070]爱情之路
[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!’
输入示例
4 4 1 2 1 L 2 1 1 O 1 3 1 V 3 4 1 E
输出示例
4 1
数据规模及约定
对于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]爱情之路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。