酷暑一夏1

不忘初心,方得始终


Vijos1411 Dejected Birthday-允诺 题解

题目

9.19是青子的生日…
而在那日晚,基德发出了盗窃”忧郁的生日”的预告函.
快斗在两难的抉择下,最终决定:以最快速度将”忧郁的生日”收入囊中,再赶去为青子表演魔术–这是他对青子的允诺.
“忧郁的生日”被保存在一个深不可测的大楼里.而从大门到最里面的房间有无数条路径.整个大楼可以被看做一个巨大的无向图,有些
房间之间有路,而有些没有.每条路要消耗基德不一样的时间.在最里面的房间内存放着”忧郁的生日”.这块宝石被一层密码锁保护着.
打开这层密码锁也需要一段时间.假设基德盗窃时没有人来干扰(警卫都干什么吃的).给出基德开始盗窃的时间,整个大楼中连通的情
况以及打开这个密码锁的时间.求出快斗能对青子允诺到达生日会场的最早时间.若此时间晚于24:00则输出”Sad”.

题解

把所有时间统一为秒进行计算最后转换两下即可。
(因为题目没有给数据范围,根据我AC的代码猜测,$0<n<150000, 0<m<10^8$,n为节点数,m为边数)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<queue>
const int MAXN=150000+5;
const int MAXM=100000000+5;
const int MAXL=100+5;
struct Edge{int u,v,w,next;};
int n,k,head[MAXN],dis[MAXN],cnt;Edge edge[MAXM];char inp[MAXL];bool vis[MAXN];
std::queue<int>que;
void AddEdge(int u,int v,int w)
{
Edge tmp;int &i=++cnt;
tmp.u=u;tmp.v=v;tmp.w=w;tmp.next=head[u];
edge[i]=tmp;head[u]=i;
}
void SPFA()
{
memset(dis,0x3f3f3f,sizeof(dis));
que.push(1);dis[1]=0;
while(!que.empty())
{
int u=que.front();que.pop();
vis[u]=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(!vis[v])
{
vis[v]=1;
que.push(v);
}
}
}
}
}
int main()
{
int x,y,z,h,m;
scanf("%d:%d",&h,&m);
scanf("%d %d",&n,&k);
for(int i=1;i<=k;i++)
{
scanf("%d %d %d",&x,&y,&z);
z*=60;
if(!x || !y) continue;
AddEdge(x,y,z);AddEdge(y,x,z);
}
SPFA();
scanf("%s",inp);
x=strlen(inp);y=0;
for(int i=0;i<x;i++)
if(inp[i]>='0' && inp[i]<='9') y=y*10+inp[i]-'0'; else {z=i;break;}
if(inp[z]=='h') y*=3600; else if(inp[z]=='m') y*=60;
z=h*3600+m*60+y+dis[n];
if(z>86400)
{
printf("Sad");
}
else
{
printf("%d",z/3600);
printf(":");
y=(z/60)%60;
if(y<10) printf("0");
printf("%d",y);
}
return 0;
}
最近的文章

Vijos1876 小岛的标号 题解

题目Xiaodao是一位喜欢参加ACM比赛的孩子.所谓ACM比赛, 是一种团队比赛.每一次比赛, 每队需要由恰好三位选手组成.现在, Xiaodao希望组建一支新的队伍, 在这之前, 他需要知道每一位朋友有多少可能成为自己的好队友.他计划给每一位朋友做出一个等级标号.Xiaodao本人的等级标号为0 …

于  Vijos, 中秋节模拟赛之冷月葬花魂 继续阅读
更早的文章

Vijos 基础01背包问题 1133 装箱问题,1104 采药,1025 小飞侠的游园方案 题解

题目略 题解直接套模版。装箱问题需要输出$V-dp[n][V]$,其它输出$dp[n][V]$。 代码1234567891011121314151617181920//1025#include&lt;cstdio&gt;#include&lt;algorithm&gt;const int MAXN= …

于  01背包, Vijos, 问题集合 继续阅读