OJ_电子地图

题干

小明是今年参加复试的外校考生，他要去民主楼小礼堂签到。由于对中南大学校本部很不熟悉，小明找到了这边读书的好朋友鲁大师，不巧，鲁大师在忙着自由探索项目的结题工作，不能给他带路，只好给他发了一份半成品的电子地图。地图上只列出了校本部内的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;
}