题目描述
小明是今年参加复试的外校考生,他要去民主楼小礼堂签到。由于对中南大学校本部很不熟悉,小明找到了这边读书的好朋友鲁大师,不巧,鲁大师在忙着自由探索项目的结题工作,不能给他带路,只好给他发了一份半成品的电子地图。地图上只列出了校本部内的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
分析:为dijkstra算法的变形
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define MAX 1005 int n,m,s,t,a; int visited[MAX]; int map[MAX][MAX]; int dist[MAX]; int wt[MAX]; void dijkstra(){ memset(visited,0,sizeof(visited)); if(s % 2) wt[s] = 1; else wt[s] = 2; for(int i = 1; i <= n; i ++){//初始化 dist[i] = map[s][i] + wt[s]; } visited[s] = 1; for(int i = 1; i < n; i ++){ int min = INF,pos; for(int j = 1; j <= n; j ++){ if(!visited[j] && min >dist[j]){ min = dist[j]; pos = j; } } visited[pos] = 1; if(pos % 2) wt[pos] = 1; else wt[pos] = 2; for(int j = 1; j <= n; j ++){//更新数组 if(!visited[j] && dist[j] > dist[pos] + map[pos][j] + wt[pos]){ dist[j] = dist[pos] + map[pos][j] + wt[pos]; } } } } int main() { int x,y,z; while(scanf("%d%d%d%d%d",&n,&m,&s,&t,&a) != EOF){ memset(map,INF,sizeof(map)); for(int i = 1; i <= n; i ++){ map[i][i] = 0; } for(int i = 1; i <= m; i ++){ scanf("%d%d%d",&x,&y,&z); map[x][y] = map[y][x] = z; } dijkstra(); if(dist[t] <= a) printf("YES %d\n",dist[t]); else printf("KENG\n"); } return 0; }
参考链接:(5条消息) PIPIOJ 1010: 好坑的电子地图_「已注销」的博客-CSDN博客_pipi好坑的电子地图
题目链接:PIPIOJ
标签:dist,int,MAX,pos,电子地图,wt,PIPOJ From: https://www.cnblogs.com/8023yyl/p/17090691.html