题目链接:https://vijos.org/p/1411

背景

9.19是青子的生日...
而在那日晚,基德发出了盗窃"忧郁的生日"的预告函.
快斗在两难的抉择下,最终决定:以最快速度将"忧郁的生日"收入囊中,再赶去为青子表演魔术--这是他对青子的允诺.

题目描述

"忧郁的生日"被保存在一个深不可测的大楼里.而从大门到最里面的房间有无数条路径.整个大楼可以被看做一个巨大的无向图,有些
房间之间有路,而有些没有.每条路要消耗基德不一样的时间.在最里面的房间内存放着"忧郁的生日".这块宝石被一层密码锁保护着.
打开这层密码锁也需要一段时间.假设基德盗窃时没有人来干扰(警卫都干什么吃的).给出基德开始盗窃的时间,整个大楼中连通的情
况以及打开这个密码锁的时间.求出快斗能对青子允诺到达生日会场的最早时间.若此时间晚于24:00则输出"Sad".

输入格式

输入文件共k+3行.
第一行,是基德开始盗窃的时间.格式为形如"xx:xx"的24小时制形式(如13:00);
第二行到第k+2行为大楼的连通情况.
第二行共2个整数n,k.n为房间总数,共k对房间之间有路径.进口为1号房间,"忧郁的生日"存放在n号房间里.
第三行到第k+2行,每行共3个整数a,b,c.表示a号和b号房间之间有路径,该路径费时为c分钟.
第k+3行为打开密码锁的时间,格式为"x min/second/hour"表示打开密码锁需要x分钟/秒/小时.

输出格式

输出共一行,输出快斗能允诺青子的最早时间,格式如同输入中的开始盗窃时间格式"xx:xx",24小时制.若最早时间超过24:00则输出
"Sad".

样例输入

17:00
3 3
1 2 1
2 3 1
1 3 4
3min

样例输出

17:05

提示

数据保证一定能抵达中心房间。需要注意的是，输入数据中可能会出现0号结点。这些数据均需被忽略不计。而输入中开始时间必定
遵守"xx:xx"格式，如"05:00";但输出中你必须这样表示:"5:00"而不应出现一开始的“0”。

来源

From 玛维-影之歌
永远守望vijos...

解题思路

最短路走一波。。。

#include <stdio.h>
#define MAXN 1010
const int inf = 99999999;
int n, m, vis[MAXN], dis[MAXN], map[MAXN][MAXN];
void Dijkstra(int s)
{
    int k, minn;
    for (int i = 1; i <= n; i++)
    {
        vis[i] = 0;
        dis[i] = inf;
    }
    dis[s] = 0;
    for (int i = 0; i < n; i++)
    {
        k = s;
        minn = inf;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dis[j] < minn)
                minn = dis[k = j];
        vis[k] = 1;
        for (int j = 1; j <= n; j++)
            if (map[k][j] < inf)
                if (!vis[j] && dis[j] > dis[k] + map[k][j])
                    dis[j] = dis[k] + map[k][j];
    }
}
int main()
{
    char str[10];
    int ah, am, as, u, v, w;
    while (~scanf("%d:%d", &ah, &am))
    {
        as = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                map[i][j] = inf;
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            if (u && v)
                map[u][v] = map[v][u] = w;
        }
        scanf("%s", str);
        for (int i = 0; str[i]; i++)
        {
            if (str[i] >= '0' && str[i] <= '9')
                as = as * 10 + str[i] - '0';
            else if (str[i] != 's')
            {
                if (str[i] != 'm')
                    as *= 3600;
                else as *= 60;
                break;
            }
            else break;
        }
        Dijkstra(1);
        as += ah * 3600 + (am + dis[n]) * 60;
        if (as > 24 * 3600)
            printf("Sad\n");
        else printf("%d:%02d\n", as / 3600, as % 3600 / 60);
    }
    return 0;
}