3040049_ac_312ms_520k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 327 行

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define MaxTry 3
#define INF 2100000000

using namespace std;

char stop[1001][31];
int no;
struct node
{
	int tar, w;
	int route;
	int pos;
};

vector <node> edge[1001];
int ts[1001][61], sum[1001][102];
int dis1[1001], dis2[1001];
int trycnt[1001];

int getId(char name[])
{
	int i;

	for(i = 0; i < no; i++)
	{
		if(strcmp(name,stop[i])==0)
		{
			return i;
		}
	}
	strcpy(stop[no],name);
	return no++;
}

int findId(char name[])
{
	int i;

	for(i = 0; i < no; i++)
	{
		if(strcmp(name,stop[i])==0)
		{
			return i;
		}
	}
	return -1;
}

struct Node
{
	int dis;
	int h, m;
	int pos;
	int id, route;
};

void OLE()
{
	while(1)
	{
		puts("I Love SqL");
	}
}

void bfs(int id,char st[],int dis[])
{
	int i, j, h, m, wait;
	queue <Node> que;
	Node p, s;
	node q;

	memset(trycnt,0,sizeof(trycnt));
	h = atoi(st);
	m = 1;
	if(st[m]!=':')
	{
		m++;
	}
	m = atoi(&st[m+1]);
	for(i = 0; i < no; i++)
	{
		dis[i] = INF;
	}
	dis[id] = 0;
	p.id = id;p.h = h;p.m = m;p.route = -1;p.dis = 0;p.pos = -1;
	que.push(p);
	while(!que.empty())
	{
		p = que.front();
		que.pop();
		for(i = 0; i < edge[p.id].size(); i++)
		{			
			q = edge[p.id][i];
			s.h = p.h;s.m = p.m;
			s.id = q.tar;
			if(p.route==-1)
			{
				wait = INF;
				for(j = 1; j <= ts[q.route][0]; j++)
				{
					int tt = (ts[q.route][j]+sum[q.route][q.pos-1])%60-p.m;
					if(tt<0)
						tt += 60;
					if(tt < wait)
					{
						wait = tt;
					}
				}
				wait += q.w;
				if(wait + p.dis < dis[q.tar])
				{
					s.dis = dis[q.tar] = wait+p.dis;
					s.route = q.route;
					s.m += wait;
					if(s.m >= 60)
					{
						s.h += s.m/60;
						s.m = s.m%60;
					}
					s.pos = q.pos;
					que.push(s);
				}
				continue;
			}
			if(p.route==q.route&&q.pos==p.pos+1)
			{
				wait = q.w;
				if(wait + p.dis < dis[q.tar])
				{
					s.dis = dis[q.tar] = wait+p.dis;
					s.route = q.route;
					s.m += wait;
					if(s.m>=60)
					{
						s.h += s.m/60;
						s.m = s.m%60;
					}
					s.pos = q.pos;
					que.push(s);
				}
				continue;
			}
			wait = INF;
			for(j = 1; j <= ts[q.route][0]; j++)
			{
				int tt = (ts[q.route][j]+sum[q.route][q.pos-1])%60-p.m;
				if(tt<0)
					tt += 60;
				if(tt >= 2&&tt < wait)
				{
					wait = tt;
				}
			}
			wait += q.w;
			int mark = 0;
			if(dis[q.tar] > p.dis+wait)
			{
				mark = 1;
				s.dis = dis[q.tar] = p.dis+wait;
			}
			if(mark||trycnt[s.id]<MaxTry)
			{
				trycnt[s.id] ++;
				s.dis = p.dis+wait;
				s.m += wait;
				if(s.m >= 60)
				{
					s.h += s.m/60;
					s.m = s.m%60;
				}
				s.pos = q.pos;
				s.route = q.route;
				que.push(s);
			}
		}
	}
}

struct NODE
{
	int h, m;

	bool operator >  (const NODE &x) const
	{
		if(x.h<h||(x.h==h&&x.m<m))
			return true;
		else
			return false;
	}
	bool operator <  (const NODE &x) const
	{
		if(x.h>h||(x.h==h&&x.m>m))
			return true;
		else
			return false;
	}
}t1[1001], t2[1001], tt;

NODE max(NODE a,NODE b)
{
	return a > b ? a : b;
}

NODE min(NODE a,NODE b)
{
	return a < b ? a : b;
}

int main()
{
	int i, j, L, c, c1, c2, prev, now;
	char st[31], ed[31], tmp[31];
	node t;
	int h, m, error, pos;

	while(scanf("%d",&L)==1,L>=0)
	{
		error = 0;
		for(i = 0; i < 1001; i++)
		{
			edge[i].clear();
		}
		no = 0;
		for(i = 0; i < L; i++)
		{
			scanf("%s",st);
			prev = getId(st);
			sum[i][0] = 0;
			pos = 1;
			scanf("%d",&c);
			while(c!=-1)
			{
				scanf("%s",st);
				now = getId(st);
				t.route = i;
				t.tar = now;
				t.w = c;
				sum[i][pos] = sum[i][pos-1]+c;
				scanf("%d",&c);
				t.pos = pos++;
				edge[prev].push_back(t);
				prev = now;
			}
			scanf("%d",&ts[i][0]);
			for(j = 1; j <= ts[i][0]; j++)
			{
				scanf("%d",&ts[i][j]);
			}
		}
		scanf("%s%s",st,tmp);
		c1 = findId(tmp);
		if(c1==-1)
		{
			error = 1;
			goto next;
		}
		h = atoi(st);
		m = 1;
		if(st[m]!=':')
		{
			m++;
		}
		m = atoi(&st[m+1]);
		bfs(c1,st,dis1);
		for(i = 0; i < no; i++)
		{
			t1[i].h = h;
			t1[i].m = m+dis1[i];
			if(t1[i].m >= 60)
			{
				t1[i].h += t1[i].m/60;
				t1[i].m = t1[i].m%60;
			}
		}
next:
		scanf("%s%s",ed,tmp);
		c2 = findId(tmp);
		if(error||c2==-1)
		{
			puts("No connection");
			continue;
		}
		h = atoi(ed);
		m = 1;
		if(ed[m]!=':')
		{
			m++;
		}
		m = atoi(&ed[m+1]);
		bfs(c2,ed,dis2);
		error = 1;
		for(i = 0; i < no; i++)
		{
			if(dis1[i]!=INF&&dis2[i]!=INF)
			{
				error = 0;
				break;
			}
		}
		if(error)
		{
			puts("No connection");
			continue;
		}
		for(i = 0; i < no; i++)
		{
			t2[i].h = h;
			t2[i].m = m+dis2[i];
			if(t2[i].m >= 60)
			{
				t2[i].h += t2[i].m/60;
				t2[i].m = t2[i].m%60;
			}
		}
		tt = max(t1[0],t2[0]);
		for(i = 1; i < no; i++)
		{
			tt = min(tt,max(t1[i],t2[i]));
		}
		printf("%d:%02d\n",tt.h%24,tt.m%60);
	}
	return 0;
}