首页 > 试题广场 >

共享单车

[编程题]共享单车
  • 热度指数:1269 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给出一张图,图上有 n 个节点,从 1 到 n 编号,和 m 条边,每条边有一个权重,表示小明走路通过这条边的时间,所有边都是无向的。

小明从 1 号节点出发,他要去 n 号节点,他想用的总时间尽可能的短。小明有共享单车 APP ,图上有些节点有共享单车,当他到达一个有车节点后,他就可以一直骑车,如果一条边走路通过的时间是 t ,那么骑车通过的时间就是 t/2 ,这里的除法是向下取整,如 t = 1 时 t/2 = 0,t = 2时,t/2 = 1。
小明可以先走到一个节点取车再骑车过去,也可以直接走过去,问他在最优策略下,需要多少时间从 1 到 n。

数据范围:   

输入描述:
第一行两个数 n,m ,接下来有 m 行,每行三个数 u,v,w ,表示 u 和 v 之间有一条边权为 w 的无向边
接下来一个数 k ,表示有 k 个节点有车,最后输入 k 行,表示有车节点的编号
输入的图中可能有自环和重边




输出描述:
输出一个数,从 1 到 n 的最少所需的时间,如果 1 和 n 不连通,输出 -1
示例1

输入

4 3
1 3 1
1 2 3
2 4 4
1
3

输出

4

说明

小明走过去拿到车,然后骑车去目的地,路线入图:

/* 思路:分层图最短路,在最短路基础上加一维是否骑车即可。 */

#include <bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int AX = 1e5 + 666 ;
int n , m ;
int tot ;
int mark[AX] ;
int vis[5][AX] ;
struct Node {
    int v , w , nxt ;
    Node() {}
    Node( int v , int w , int nxt ):v(v),w(w),nxt(nxt) {}
} G[AX<<1];
struct RES {
    int u , sta ;
    LL w ;
    RES() {}
    RES( int u , int sta , LL w ):u(u),sta(sta),w(w) {}
    bool operator < ( const RES &a )const {
        return w > a.w ;
    }
};
int head[AX] ;
LL dis[5][AX] ;
void add( int u , int v , int w ) {
    G[tot] = Node( v , w , head[u] ) ;
    head[u] = tot++ ;
    G[tot] = Node( u , w , head[v] ) ;
    head[v] = tot++ ;
}
void dijstra() {
    priority_queue q;
    if( mark[1] ) {
        q.push(RES(1,1,0)) ;
        dis[1][1] = 0 ;
    }
    q.push(RES(1,0,0)) ;
    dis[0][1] = 0 ;

    while( !q.empty() ) {
        RES tmp = q.top() ;
        q.pop() ;
        int u = tmp.u ;
        int sta = tmp.sta ;
        vis[sta][u] = 1 ;
        for( int i = head[u] ; ~i ; i = G[i].nxt ) {
            int v = G[i].v ;
            LL w = G[i].w ;
            if( sta == 1 && !vis[1][v] && dis[1][v] > dis[1][u] + (LL)(w / 2) ) {
                dis[1][v] = dis[1][u] + (LL)(w / 2) ;
                q.push(RES(v,1,dis[1][v]));
            }
            if( sta == 0 && !vis[0][v] && dis[0][v] > dis[0][u] + w ) {
                dis[0][v] = dis[0][u] + w ; 
                q.push(RES(v,0,dis[0][v]));
            }

            if( sta == 0 && mark[v] && !vis[1][v] && dis[1][v] > dis[0][u] + w ){
                dis[1][v] = dis[0][u] + w ; 
                q.push(RES(v,1,dis[1][v]));
            }

        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    int x , y , w , k ;
    memset( head , -1 , sizeof(head) ) ;
    memset( vis , 0 , sizeof(vis) );
    memset( mark , 0 , sizeof(mark) );
    memset( dis , 0x3f , sizeof(dis) );
    tot = 0 ;
    for( int i = 0 ; i < m ; i++ ) {
        scanf("%d%d%d",&x,&y,&w);
        if( x == y ) continue ;
        add( x , y , w ) ;
    }
    scanf("%d",&k);
    for( int i = 0 ; i < k ; i++ ) {
        scanf("%d",&x);
        mark[x] = 1 ;
    }
    dijstra();
    if( dis[0][n] == INF && dis[1][n] == INF ) printf("-1\n");
    else printf("%lld\n",min(dis[0][n],dis[1][n]));
    return 0 ;
}

编辑于 2020-04-18 18:39:56 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct Edge{
    int v, w;
};

struct P{
    int id;
    long s;
    bool flag;
};

struct cmp{
    bool operator()(const P &p1, const P &p2)const{
        return p1.s > p2.s;
    }
};

long vis[100003][2];
bool mp[100003] = {false};

int main(){
    memset(vis, 0x3f3f, sizeof(vis));
    memset(mp, false, sizeof(mp));
    int n, m, u, v, w, k;
    long t;
    scanf("%d%d", &n, &m);
    vector<Edge> G[n+1];
    for(int i=0;i<m;i++){
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    scanf("%d", &k);
    while(k--){
        scanf("%d", &u);
        mp[u] = true;
    }
    priority_queue<P, vector<P>, cmp> q;
    q.push({1, 0, mp[1]});
    vis[1][mp[1]] = 0;
    while(!q.empty()){
        P p = q.top();
        q.pop();
        if(p.id == n){
            printf("%ld\n", p.s);
            return 0;
        }
        for(auto &e: G[p.id]){
            if(p.flag)
                t = p.s + e.w/2;
            else
                t = p.s + e.w;
            bool flag = p.flag | mp[e.v];
            if(t < vis[e.v][flag]){
                vis[e.v][flag] = t;
                q.push({e.v, t, flag});
            }
        }
    }
    printf("-1\n");
    return 0;
}

发表于 2020-09-09 01:24:14 回复(0)