某R开头公司在Hackerrank上的一道3小时面试题_hackerrank 面试

题目：

在世界的某个地方（具体记不清了，好像是北极附近）有一些岛（Vertices）和岛之间的桥（Edges）。因为气温太低，有些桥比较人性化，桥面安装了加热设备（HOT BRIDGES），但为了省钱（或是其他原因，记不清了）不是所有桥都装有加热设备 (COLD BRIDGES)。假设一个人从某个岛（Source）通过一些桥去往另一个岛（Destination），求满足以下条件的最短路径（Djistra）是否存在：

1. 该人必须交替使用COLD和HOT的桥，即如果上一个走到桥是HOT，下一个走的必须是COLD，vice versa （理由是连续走两个COLD会冻死，连续走两个HOT会热死）。

2. 两个岛之间可能会有两座桥，一座HOT，一座COLD。

3. 桥是单向的（有向边）。

程序有如下一些约束条件：

1. 输入是STDIN，输出是STDOUT。

2. 桥的个数和岛的格式在Int表示范围内

3. 输入格式如下：

2

2 1 0 1

0 1 HOT

2 1 0 1

0 1 COLD

其中第一行的“2”表示程序有两个测试用例。 接下来的 2 1 0 1 表示2个顶点，1条边，起点为0号顶点，终点为1号顶点。接下来的 0 1 HOT为边的描述：从0到1的一条HOT边。接下来的2 1 0 1是第二个测试用例，定义如上。