1010: 好坑的电子地图

题目描述
小明是今年参加复试的外校考生，他要去民主楼小礼堂签到。由于对中南大学校本部很不熟悉，小明找到了这边读书的好朋友鲁大师，不巧，鲁大师在忙着自由探索项目的结题工作，不能给他带路，只好给他发了一份半成品的电子地图。地图上只列出了校本部内的N个点，M条路，小明处于S点，民主楼小礼堂是T点。小明感谢鲁大师，当然只是在拿到地图的一瞬间，后面的情况让他知道这半成品到底有多坑。鲁大师制作的电子地图是带有语音提示功能的，但是在编号为奇数的点他要等1分钟才能告诉他具体怎么走，而在编号为偶数的点要等2分钟。现在告诉你地图的具体情况，小明想知道他能不能在A分钟内赶到民主楼小礼堂。

输入
输入数据有多组，每组占M+1行，第一行有5个数字N，M，S，T，A，接下来M行，每行三个数字u,v,t，代表每条路的两个顶点和步行时间。（输入数据保证不含重边0<N<M<1000）

输出
对于每组输入数据，输出一行，小明能在A分钟内赶到民主楼小礼堂输出YES和最少花费的时间，否则输出KENG

样例输入
4 3 1 4 10
1 2 1
3 2 2
3 4 3
5 4 2 4 7
1 2 5
5 4 2
3 5 1
2 3 1

样例输出
YES 10
KENG

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
const int maxn=1005;
const int INF=INT_MAX;
int n,m,s,t,a;
struct node
{
	int to;
	int time;
	node():to(0),time(0){}
	node(int t,int time):to(t),time(time){}
};
struct point
{
	int po;
	int lowest_time;
	point(int p,int l):po(p),lowest_time(l){}
	bool operator< (const point &temp) const{
		return lowest_time>temp.lowest_time;
	}
};

vector<node>g[maxn];

int lowtime[maxn];

void initial()
{
	for(int i=0;i<maxn;i++)
	{
		g[i].clear();
		lowtime[i]=INF;
	}
}

void dijkstra(int s)
{
	priority_queue<point>q;
	lowtime[s]=0;
	q.push(point(s,0));
	while(!q.empty())
	{
		int u=q.top().po;
		q.pop();
		for(int i=0;i<g[u].size();i++)
		{//以u为中间点，从s到g[u][i].to(to1);
			int to1=g[u][i].to;
			int time1=g[u][i].time; 
			
				if(u%2==0&&lowtime[to1]>lowtime[u]+time1+2)
				{	
					lowtime[to1]=lowtime[u]+time1+2;
					q.push(point(to1,lowtime[to1]));
				} 
				else if(u%2!=0&&lowtime[to1]>lowtime[u]+time1+1)
				{
					lowtime[to1]=lowtime[u]+time1+1;
					q.push(point(to1,lowtime[to1]));
				}		
		
		}
	}
}
int main()
{
	while(scanf("%d%d%d%d%d",&n,&m,&s,&t,&a)!=EOF)
	{
		initial();
		int u,v,ti;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&ti);
			g[u].push_back(node(v,ti));
			g[v].push_back(node(u,ti));
		}
		dijkstra(s);
		if(lowtime[t]>a) printf("KENG\n");
		else printf("YES %d\n",lowtime[t]);
	}
	return 0;
}