acwing 3653. 好坑的电子地图 最短路 dijkstra算法

题目背景

地图上只列出了校本部内的N个点，M条双向道路，小明处于S点，民主楼小礼堂是 T点。电子地图是带有语音提示功能的，但是在编号为奇数的点他要等1分钟才能告诉他具体怎么走，而在编号为偶数的点要等 2分钟。现在告诉你地图的具体情况，小明想知道他能不能在 A分钟内赶到民主楼小礼堂。

输入格式

输入包含多组测试数据。
每组数据第一行包含 5个整数，N,M,S,T,A。接下来 M行，每行三个数字 u,v,t 代表每条路的两个顶点和步行时间。

输出格式

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

数据范围

0<N<M<1000,
1≤S,T,u,v≤N,
1≤A,t≤1000

输入样例：

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<bits/stdc++.h>using namespace  std;const int N = 1010,INF = 0x3f3f3f3f;int n,m,S,T,A;
int g[N][N];
int dist[N];  //到起点s的距离
bool st[N];int dij(int s){dist[s] = 0;for(int i=0; i < n; i++){int t = -1;for(int i = 1; i<= n; i++ )if(!st[i] && (t==-1 || dist[t]>dist[i])) t = i;for(int i = 1; i<= n; i++ )dist[i] = min(dist[i],dist[t] + g[t][i]);st[t] = true;}return dist[T];
}int main(){while(cin>>n>>m>>S>>T>>A){memset(g,0x3f,sizeof g);memset(dist,0x3f,sizeof dist);memset(st,0,sizeof st); while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);int gap1 = b%2? 1:2;int gap2 = a%2? 1:2;g[a][b] = min(g[a][b],c+gap2);g[b][a] = min(g[b][a],c+gap1);}int time = dij(S);//S点到T的距离if(time <= A ) cout<<"YES"<<" "<<time<<endl;else cout<<"KENG"<<endl;}return 0;
}

和上面一道题一样