#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; }
|