题干
小明是今年参加复试的外校考生，他要去民主楼小礼堂签到。由于对中南大学校本部很不熟悉，小明找到了这边读书的好朋友鲁大师，不巧，鲁大师在忙着自由探索项目的结题工作，不能给他带路，只好给他发了一份半成品的电子地图。地图上只列出了校本部内的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
c++实现
#include <iostream>
#include <vector>
using namespace std;
const int inf = 99999999;//不可到达
int main()
{
int n, m, s, t, a;
while (cin >> n >> m >> s >> t >> a)
{
vector<vector<int>> e(n + 2, vector<int>(n + 2)); //邻接矩阵
vector<int> dis(n + 2, inf); //保存到t点的路程
vector<bool> visit(n + 2, false); //标记当前节点是否访问过
for (int i = 1; i <= n; i++) //初始化二维数组，对角线被初始化为0
{
for (int j = 1; j <= n; j++)
{
if (i == j)
{
e[i][j] = e[j][i] = 0;
}
else
{
e[i][j] = e[j][i] = inf;
}
}
}
for (int i = 0; i < m; i++)
{
int n1, n2, c;
cin >> n1 >> n2 >> c;
e[n1][n2] = e[n2][n1] = c;
}
//Dijkstra算法部分
dis[s] = 0; //表示从出发点到i节点的距离
int wait = 0, u = -1; //在奇数顶点等1分钟，在偶数顶点等2分钟
for (int i = 1; i <= n; i++)
{
int minn = inf;
for (int j = 1; j <= n; j++)
{
if (visit[j] == false && dis[j] < minn) //更新dis数组
{
u = j;
minn = dis[j];
}
}
if (u == -1) //u=-1表示未找到最短路径
{
break;
}
visit[u] = true; //开始访问u顶点
if (u % 2 == 0) //在奇数顶点等1分钟，在偶数顶点等2分钟
{
wait = 2;
}
else
{
wait = 1;
}
for (int v = 1; v <= n; v++)
{
if (visit[v] == false && e[u][v] != inf && dis[u] + e[u][v] + wait < dis[v])
{
dis[v] = dis[u] + e[u][v] + wait;
}
}
}
if (dis[t] <= a)
{
cout << "YES " << dis[t] << endl;
}
else if (dis[t] > a || u == -1)
{
cout << "KENG" << endl;
}
}
return 0;
}
