状态 耗时 内存占用

#1 Accepted 4ms 2.688 MiB
#2 Accepted 4ms 2.668 MiB
#3 Accepted 4ms 2.625 MiB
#4 Accepted 4ms 2.613 MiB
#5 Accepted 4ms 2.625 MiB
#6 Accepted 4ms 2.625 MiB
#7 Accepted 7ms 2.723 MiB
#8 Accepted 6ms 2.75 MiB
#9 Accepted 4ms 2.695 MiB
#10 Accepted 4ms 2.625 MiB
dijkstra + 堆

#include<bits/stdc++.h>
using namespace std;
const int N = 100001;
#define P pair<int,int>
#define ti first
#define x second
int hour,mine,n,m,second,t;
char ch;
int dis[N];
priority_queue<P>q;
vector<P>g[N];
int dijkstra(int s)
{
    q.push(make_pair(0,s));
    for(int i=1;i<=n;i++)
        dis[i]=0x7fffffff;
    dis[s]=0;
    while(!q.empty())
    {
        P f=q.top();q.pop();
        for(int i=0;i<g[f.x].size();i++)
        {
            P y=g[f.x][i];
            if(dis[y.x]>y.ti+f.ti)
                q.push(make_pair(dis[y.x]=y.ti+f.ti,y.x));
        }
    }
    return dis[n];
}
int main() {
    scanf("%d:%d",&hour,&mine);
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        g[u].push_back(make_pair(w,v));
        g[v].push_back(make_pair(w,u));
    }
    mine+=dijkstra(1);
    scanf("%d%c",&t,&ch);
    if (ch=='s') second += t;
    else if(ch=='m') mine += t;
    else hour+=t;
    mine+=second/60;
    hour+=mine/60;
    mine%=60;
    if(hour>24) puts("Sad");
    else printf("%d:%02d\n",hour,mine);
    return 0;
}

为啥其他题解都是几年前的啊

MDZZ竟然被**读入优化**毒奶了一口，TAT。。。。
手贱加了一个加号，就无限TLE了，唉~（蓝瘦香菇.jpg）；

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 13180 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 13180 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 13184 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 13180 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 13180 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 13184 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 13176 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 13180 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 13176 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 13180 KiB, score = 10
Accepted, time = 0 ms, mem = 13184 KiB, score = 100

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 100001
using namespace std;
char ch;
int mine = 0,second = 0,hour = 0,t,k = 0;
int head[N],dis[N],n,m;
bool vis[N] = {0};
struct node {
    int w,to,next;
}e[10*N];
inline int read() {
    int t = 1,x = 0;
    char c = getchar();
    while ( c < '0' || c > '9' ) {
        if ( c == '-' ) t = -1;
        c = getchar();
    }
    while ( c >= '0' && c <= '9' ) {
        x = x*10 + c - '0';
        c = getchar();
    }
    return t * x;
}
inline void add(int u,int v,int w) {
    e[k].to = v,e[k].next = head[u],e[k].w = w;
    head[u] = k++;
    e[k].to = u,e[k].next = head[v],e[k].w = w;
    head[v] = k++;
}
int spfa() {
    queue<int> q;
    dis[1] = 0; vis[1] = 1;
    q.push(1);
    while ( !q.empty() ) {
        int now = q.front();
        q.pop(); vis[now] = 0;
        for (int i=head[now];~i;i=e[i].next) {
            int son = e[i].to;
            if ( son == 0 ) continue;
            if ( dis[son] > dis[now] + e[i].w ) {
                dis[son] = dis[now] + e[i].w;
                if ( !vis[son] ) {
                    q.push(son);
                    vis[son] = 1;
                }
            }
        }
    }
    return dis[n];
}
int main() {
    scanf("%d:%d",&hour,&mine);
    // cout<<hour<<":"<<mine<<endl;
    n = read();  m = read();
    int u,v,w;
    memset (head,-1,sizeof head);
    for (int i=1;i<=n;i++) dis[i] = 9999;
    for (int i=1;i<=m;i++) {
        u = read(), v = read(), w = read();
        add (u,v,w);
    }
    scanf("%d%c",&t,&ch);
    if ( ch == 's' ) second += t;
    else if ( ch == 'm' ) mine += t;
    else hour += t;
    mine += spfa();
    mine += second/60;
    second %= 60;
    hour += mine/60;
    mine %= 60;
    if ( hour > 24) printf("Sad\n");
    else
        printf("%d:%02d",hour,mine);
    return 0;
}

AC50 留念

var a:array[0..1000,0..1000]of longint;
dis,h:array[0..1000000]of longint;
i,n,k,x,y,z,ans:longint; s:string;
procedure spfa(x:longint);
var tou,wei,i,j:longint;
begin
for i:=1 to n*2 do dis[i]:=10000000;
tou:=0; wei:=1;
dis[x]:=0;
h[1]:=x;
while tou<>wei do
begin
inc(tou);
x:=h[tou];
for i:=1 to n do
if (a[x,i]<>0)and(dis[x]+a[x,i]<dis[i]) then
begin
dis[i]:=dis[x]+a[x,i];
inc(wei);
h[wei]:=i;
end;
end;
end;
begin
readln(s);
ans:=((ord(s[1])-48)*10+ord(s[2])-48)*60+(ord(s[4])-48)*10+ord(s[5])-48;
readln(n,k);
for i:=1 to k do
begin
readln(x,y,z);
a[x,y]:=z;
a[y,x]:=z;
end;
spfa(1);
ans:=ans+dis[n];
readln(s);
k:=0;
for i:=1 to length(s) do
if (s[i]>='0')and(s[i]<='9') then
k:=k*10+ord(s[i])-48;
for i:=1 to length(s) do
begin
if s[i]='m' then ans:=ans+k;
if s[i]='h' then ans:=ans+k*60;
if s[i]='s' then ans:=ans+k div 60;
end;
if ans div 60>24 then writeln('Sad') //此句三十分
else
begin
write(ans div 60,':');
ans:=ans mod 60;
if ans<10 then writeln('0',ans) else writeln(ans);
end;
end.

题目表述不清！注意：
1.秒舍去
2.端点为0时算一条边（计数+1）但不读入！

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>

//#define debug

using std::queue;
using std::cin;

struct edge{
int d,v;
struct edge *link;
};

int top=1,n,m;
edge graph[10000]={0};
edge node[1000000];
int lock;

void read(int s,int d,int v){
edge *l;
l=&node[top];
l->d=d;
l->v=v;
l->link=graph[s].link;
graph[s].link=l;
top++;
}

void build(){
scanf("%d%d",&n,&m);
int s,d,v;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&s,&d,&v);

if(s==0||d==0){
// i--; //ignore 0
continue;
}
v=v*60; //min to sec

read(s,d,v);
read(d,s,v);
}
}

//SPFA

int inque[10000]={0};
int dist[10000];
queue <int> q;

void spfa(int s){
for(int i=1;i<=n;i++)
dist[i]=9999999;

q.push(s);
inque[s]=1;
dist[s]=0;
edge *l;
int t;
while(!q.empty()){
t=q.front();
q.pop();
inque[t]=0;
l=graph[t].link;
while(l){
if(dist[t]+l->v<dist[l->d]){
dist[l->d]=dist[t]+l->v;
// dist[next]>dist[now]+value)
if(!inque[l->d]){
q.push(l->d);
inque[l->d]=1;
}
}
l=l->link;
}
}
}

int gettime(){
int t,re;
char type[100];
cin>>t>>type;
if(type[0]=='s')
re=t;
if(type[0]=='m')
re=60*t;
if(type[0]=='h')
re=60*60*t;
return re;
}

int main(){
#ifdef debug

freopen("in.txt","r",stdin);

#endif

int starthh,startmm;
scanf("%d:%d",&starthh,&startmm);

build();
gettime();
lock=gettime(); //sec
spfa(1);
int usesec=dist[n]+lock; //开始没加第一个房间
int hour=0,min=0;
min=usesec/60+startmm;
hour+=min/60;
min%=60;
hour+=starthh;

if(hour>24){
printf("Sad");
return 0;
}

if(hour==24&&min>0){
printf("Sad");
return 0;
}

printf("%d:%02d",hour,min);

return 0;
}

NOIP2014赛前AC留念
（运动会ing~~~~~~
WA这么多次我也是醉了
字符串的处理总是那么奇妙）
var t1,s,tip,time:string;
hour,max,a,kk,b,c,min,n,k,i,j:longint;
dist:array[0..10000] of longint;
cost:array[0..6000,0..6000] of longint;
use:array[0..10000] of boolean;
ch:char;

procedure dijkstra;
var i,j,min,pos:longint;
begin
for i:=1 to n do dist[i]:=maxlongint;
dist[1]:=0;
for i:=1 to n-1 do
begin
min:=maxlongint;
for j:=1 to n do
if not use[j] then
if dist[j]<min then
begin
min:=dist[j];
pos:=j;
end;
use[pos]:=true;
for j:=1 to n do
if cost[pos,j]<>0 then
if dist[pos]+cost[pos,j]<dist[j] then
dist[j]:=dist[pos]+cost[pos,j];
end;
end;

begin
//assign(input,'t3.in');
//assign(output,'t3.out');
//reset(input);
//rewrite(output);
readln(s);
tip:=copy(s,1,2);
val(tip,hour);
tip:=copy(s,4,2);
val(tip,min);
readln(n,k);
for i:=1 to k do
begin
readln(a,b,c);
if(a<>0) and (b<>0) then begin
cost[a,b]:=c;
cost[b,a]:=c;
end;
end;
dijkstra;
readln(s);
for i:=1 to length(s) do
if (s[i]<'0') or (s[i]>'9') then
begin
max:=i;
break;
end;
t1:=copy(s,1,max-1);
val(t1,kk);
time:=copy(s,max,length(s));
if time='min' then dist[n]:=dist[n]+kk;
if time='hour' then hour:=hour+kk;
if time='second' then dist[n]:=dist[n]+(kk div 60);
min:=min+dist[n] mod 60;
hour:=hour+dist[n] div 60+min div 60;
min:=min mod 60;
if (hour<24) or ((hour=24) and (min=0)) then
begin
write(hour,':');
if min<10 then write('0');
writeln(min);
end
else writeln('Sad');
//close(input);
//close(output);
end.

Block Code 好吧重发一遍

#include <cstdio>
#include <queue>
#include <cstring>
using std::queue;
#define N 1005
#define M 1000005

int n, m;
int hour, min, second;
int head[N], next[M], to[M], wei[M], cnt = 0;

int spfa(int src, int goal) {
queue<int> q;
q.push(src);
int vis[N], dist[N];
memset(vis, 0, sizeof(vis));
memset(dist, 127, sizeof(dist));
vis[src] = 1;
dist[src] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = next[i]) {
int v = to[i];
if(v == 0) continue;
if(dist[v] > dist[u] + wei[i]) {
dist[v] = dist[u] + wei[i];
if(!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
vis[u] = 0;
}
return dist[goal];
}

void add(int u, int v, int w) {
next[cnt] = head[u];
to[cnt] = v;
wei[cnt] = w;
head[u] = cnt++;
}

int main() {
scanf("%d:%d", &hour, &min);
second = 0;
scanf("%d%d", &n, &m);
int a, b, c;
memset(head, -1, sizeof(head));
while(m--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
second = 0;
min += spfa(1, n);
char ch[10];
scanf("%d%s", &m, ch);
switch(ch[0]) {
case 'm':
min += m;
break;
case 's':
second += m;
break;
case 'h':
hour += m;
break;
}
min += second / 60;
second %= 60;
hour += min / 60;
min %= 60;
if(hour > 24)
printf("Sad");
else
printf("%d:%02d", hour, min);
return 0;
}

好像没有C++的程序，我发一个吧
#include <cstdio>
#include <queue>
#include <cstring>
using std::queue;
#define N 1005
#define M 1000005

int n, m;
int hour, min, second;
int head[N], next[M], to[M], wei[M], cnt = 0;

int spfa(int src, int goal) {
queue<int> q;
q.push(src);
int vis[N], dist[N];
memset(vis, 0, sizeof(vis));
memset(dist, 127, sizeof(dist));
vis[src] = 1;
dist[src] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = next[i]) {
int v = to[i];
if(v == 0) continue;
if(dist[v] > dist[u] + wei[i]) {
dist[v] = dist[u] + wei[i];
if(!vis[v]) {
q.push(v);
vis[v] = 1;
}
}
}
vis[u] = 0;
}
return dist[goal];
}

void add(int u, int v, int w) {
next[cnt] = head[u];
to[cnt] = v;
wei[cnt] = w;
head[u] = cnt++;
}

int main() {
scanf("%d:%d", &hour, &min);
second = 0;
scanf("%d%d", &n, &m);
int a, b, c;
memset(head, -1, sizeof(head));
while(m--) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
second = 0;
min += spfa(1, n);
char ch[10];
scanf("%d%s", &m, ch);
switch(ch[0]) {
case 'm':
min += m;
break;
case 's':
second += m;
break;
case 'h':
hour += m;
break;
}
min += second / 60;
second %= 60;
hour += min / 60;
min %= 60;
if(hour > 24)
printf("Sad");
else
printf("%d:%02d", hour, min);
return 0;
}

具体的题解都发了。。
0<second<60时不算1分钟

小心min/second/hour

├ 测试数据 01：答案正确... (0ms, 11932KB)

├ 测试数据 02：答案正确... (0ms, 11932KB)

├ 测试数据 03：答案正确... (0ms, 11932KB)

├ 测试数据 04：答案正确... (0ms, 11932KB)

├ 测试数据 05：答案正确... (0ms, 11932KB)

├ 测试数据 06：答案正确... (1ms, 11932KB)

├ 测试数据 07：答案正确... (0ms, 11932KB)

├ 测试数据 08：答案正确... (0ms, 11932KB)

├ 测试数据 09：答案正确... (0ms, 11932KB)

├ 测试数据 10：答案正确... (0ms, 11932KB)

纪念第444人通过.~!!!

通过 　　444人

提交 　　1638次

编译通过...

├ 测试数据 01：答案正确... (5ms, 4512KB)

├ 测试数据 02：答案正确... (40ms, 4512KB)

├ 测试数据 03：答案正确... (40ms, 4512KB)

├ 测试数据 04：答案正确... (44ms, 4512KB)

├ 测试数据 05：答案正确... (64ms, 4512KB)

├ 测试数据 06：答案正确... (67ms, 4512KB)

├ 测试数据 07：答案正确... (48ms, 4512KB)

├ 测试数据 08：答案正确... (48ms, 4512KB)

├ 测试数据 09：答案正确... (48ms, 4512KB)

├ 测试数据 10：答案正确... (52ms, 4512KB)

贴一下小弟的程序,spfa+小小的字符串处理,大家要细心喔~!!

var

st,open:string;

tot,i,j,l,r,m,n,x,y,value,now,s,f,time:longint;

d,next,v,g,aim:array[0..1000] of longint;

q:array[0..1000000] of longint;

u:array[0..1000] of boolean;

procedure init;

begin

readln(st);

readln(n,k);

tot:=0;

for i:=1 to k do

begin

readln(x,y,value);

inc(tot); next[tot]:=y; v[tot]:=value; aim[tot]:=g[x]; g[x]:=tot;

inc(tot); next[tot]:=x; v[tot]:=value; aim[tot]:=g[y]; g[y]:=tot;

end;

readln(open);

end;

procedure spfa;

begin

fillchar(u,sizeof(u),false);

fillchar(d,sizeof(d),120);

d[1]:=0;

i:=1;

j:=1;

q[j]:=1;

while i0) then writeln('Sad') else

begin

write(s,':');

if f

清晰，一目了然的程序

program t1411;

var

a:array[1..1000,1..1000]of integer;

n,k,b,c,d,e,f,g,h,i,j,sj1,sj2,sj3,sj4:integer;

s:string;

procedure tt;

var

t:string;

begin

if s[1]='0' then t:=s[2] else t:=s[1]+s[2];

val(t,sj1,c);

if s[4]='0' then t:=s[5] else t:=s[4]+s[5];

val(t,sj2,c);

end;

procedure qq;

var

w:set of char;

t:string;

i,j:integer;

r,q:char;

begin

w:=['0'..'9'];

i:=length(s);

r:=s[i];

t:='';

for j:=1 to i do

begin

q:=s[j];

if q in w then t:=t+s[j] else break;

end;

val(t,i,j);

case r of

'n':sj2:=sj2+i;

'd':sj2:=sj2+i div 60;

'r':sj1:=sj1+i;

end;

end;

begin

readln(s);

tt;

read(n,k);

for b:=1 to n do for c:=1 to n do a:=maxint;

for b:=1 to k do begin read(f,g,h);a[f,g]:=h;a[g,f]:=h;end;

for h:=1 to n do for i:=1 to n do for j:=i to n do if a>a+a[h,j] then a:=a+a[h,j];

sj3:=a[1,n];

readln;

readln(s);

qq;

sj2:=sj2+sj3;

sj4:=sj2 div 60;

sj2:=sj2 mod 60;

sj1:=sj1+sj4;

if sj1>24 then write('Sad') else

if sj1=24 then

if sj20 then write('Sad')

else write('24:00')

else begin write(sj1,':');if sj2

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!!!

我的程序A不A和那个初始化有毛关系啊!!为什么用for初始化就10分啊啊啊啊!!

这样的一个水题我居然写了一小时......

该说的楼下的都说了。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Dijkstra的效率……果然是王道。

话说昨天我没事干，写了个深搜结果超时三个点还WA了两个点……

好吧写了88行半个多小时最后全部超时。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

SPFA，不过改得很辛苦——开始时最后出现了10:76分，忘记mod了。。。

program p1411;

type

Time = record h,m,s: integer; end;

var

s: string;

st,ed: Time;

n,m,x,y,i,h,d,u,v,z,t,r: longint;

e: array[0..1000,1..1000] of record v,w: longint; end;

p: array[0..1000] of longint;

q,dis: array[0..1000] of longint;

used: array[0..1000] of boolean;

procedure add(t:longint);

begin

if t>=3600 then begin

inc(ed.h,t div 3600);

t:=t mod 3600;

end;

if t>=60 then begin

inc(ed.m,t div 60);

t:=t mod 60;

end;

if t>0 then inc(ed.s,t);

end;

begin

readln(s);

val(s[1]+s[2],st.h);

val(s[4]+s[5],st.m);

st.s:=0;

readln(n,m);

for i:= 1 to m do begin

readln(x,y,z);

inc(p[x]);

e[x,p[x]].v:=y;

e[x,p[x]].w:=z;

inc(p[y]);

e[y,p[y]].v:=x;

e[y,p[y]].w:=z;

end;

h:=0; d:=1;

q[d]:=1; used[1]:=true;

fillchar(dis,sizeof(dis),$7f);

dis[1]:=0;

repeat

inc(h);

u:=q[(h-1) mod n+1];

for i:= 1 to p do begin

v:=e.v;

if dis+e.w=d;

readln(s);

val(s,t,r);

val(copy(s,1,r-1),t);

delete(s,1,r-1);

if s='hour' then t:=t*3600 else

if s='min' then t:=t*60;

ed:=st;

add(t);

add(dis[n]*60);

if ed.s>59 then begin

inc(ed.m,ed.s div 60);

ed.s:=ed.s mod 60;

end;

if ed.m>59 then begin

inc(ed.h,ed.m div 60);

ed.m:=ed.m mod 60;

end;

if (ed.h>=24) then writeln('Sad')

else begin

write(ed.h,':');

if ed.m

神奇的puppy啊，竟然Floyd也能过，虽然时间很丑陋。。。。。。。

还是spfa吧，秒杀

简单题。。注意看Hint就好了。。（输出的时候hour前面没有前导0..）2次AC..小烂的说。。

鄙人的程序：

正好！！

秒杀！！编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var a:array[1..500,1..500] of longint;

v:array[1..500] of boolean;

i,j,max,p,n,k,t1,x,y,maxi:longint;

s,s1:string;

aa,bb,dd:longint;

f:boolean;

begin

readln(s);

s1:=s1+s[1]+s[2];

val(s1,aa);

s1:='';

s1:=s1+s[4]+s[5];

val(s1,bb);

s1:='';

readln(n,k);

for j:=1 to k do begin readln(x,y,t1);a[x,y]:=t1;a[y,x]:=t1;end;

fillchar(v,sizeof(v),false);

v[1]:=true;

for j:=2 to n do

begin

max:=maxint;

for i:=1 to n do

if not(v[i])and(a[1,i]0)and(a[1,i]a[1,p]+a[p,i]) or(a[1,i]=0) then

a[1,i]:=a[1,p]+a[p,i];

end;

max:=a[1,n];

read(s);

for i:=1 to length(s) do

if (s[i]'9') then begin maxi:=i;break;end;

s1:=copy(s,1,maxi-1);

val(s1,dd);

s1:=copy(s,maxi,length(s));

if s1='second'then begin bb:=bb+dd div 60+max;end;

if s1='min' then begin bb:=bb+max+dd;end;

if s1='hour'then begin aa:=aa+dd;bb:=bb+max;end;

aa:=aa+bb div 60;bb:=bb mod 60;

if aa>24 then begin write('Sad');exit;end;

str(aa,s1);

if bb

4次AC，惨痛的教训

第一次和第二次都把加一写成了减一，20分

第三次超时。。，70分

第四次终于AC