首页 > 其他分享 >PIPOJ 好坑的电子地图

PIPOJ 好坑的电子地图

时间:2023-02-03 23:23:28浏览次数:64  
标签:dist int MAX pos 电子地图 wt PIPOJ

题目描述

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

相关文章

  • PIPOJ 最大连续子序列
    题目描述给定 K 个整数的序列{ N1, N2, ..., NK} ,其任意连续子序列可表示为{ Ni, Ni+1,...,Nj} ,其中1<=i<=j <=K。最大连续子序列是所有连续子序列......
  • PIPOJ 破译密码
    题目描述据说最早的密码来自于罗马的凯撒大帝。消息加密的办法是:对消息原文中的每个字母,分别用该字母之后的第5个字母替换(例如:消息原文中的每个字母A 都分别替换成字......
  • PIPOJ 惠民工程(prim算法求最小生成树)
    题目描述市政府“惠民工程”的目标是在全市n个居民点间之架设煤气管道(但不一定有直接的管道相连,只要能间接通过管道可达即可)。很显然最多可架设n(n-1)/2条管道,然而......
  • PIPOJ 最短距离
    题目描述小王和小明是好朋友,两人最开始各有一个初始位置p和一个恒定速度v,从0时刻起开始,他们从初始位置以恒定速度开始行走,请告诉我行走过程中两人的最短距离是多少......
  • 视频融合云平台EasyCVR最新版电子地图数据不显示该如何解决?
    EasyCVR视频融合云平台是基于云边端一体化架构,可在复杂的网络环境中,将分散的各类视频资源进行统一汇聚、整合、集中管理。平台可支持的协议包括:国标GB/T28181、RTMP、RTSP/......