C++ 解法, 执行用时: 55ms, 内存消耗: 8192KB, 提交时间: 2021-10-17

#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;
}

C++14 解法, 执行用时: 60ms, 内存消耗: 9980KB, 提交时间: 2020-07-28

#include<bits/stdc++.h>
using namespace std;
long visit[100005][2];
bool has_bike[100005] = {false};
struct node{
    long val;
    int index;
    bool has_bike;
    /*bool operator<(const node&n)const{
        return val>n.val; // 
    }*/
};
class comparenode{
    public:
        bool operator()(const node& lhs,const node& rhs)const{
            return lhs.val>rhs.val;
        }
};
int main(){
    memset(visit,0x3f3f,sizeof(visit));
    int n,m;
    int u,v,w;
    scanf("%d %d",&n,&m);
    vector<vector<pair<int,int> > > graph(n+1);
    for(int i=0;i<m;i++){
        scanf("%d %d %d",&u,&v,&w);
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    int k,id;
    scanf("%d",&k);
    for(int i=0;i<k;i++){
        scanf("%d",&id);
        has_bike[id] = true;
    }
    priority_queue<node,vector<node>,comparenode> q;
    q.push({0,1,has_bike[1]});
    visit[1][has_bike[1]] = 0; //
    while(!q.empty()){
        node head = q.top();
        q.pop();
        if(head.index == n){
            cout<<head.val;
            return 0;
        }
        for(pair<int,int>& nxt:graph[head.index]){
            long tim = head.val + nxt.second;
            if(head.has_bike)
                tim = head.val + (nxt.second>>1);
            if(tim<visit[nxt.first][head.has_bike|has_bike[nxt.first]]){
                visit[nxt.first][head.has_bike|has_bike[nxt.first]] = tim;
                q.push({tim,nxt.first,head.has_bike||has_bike[nxt.first]});
            }
        }
    }
    printf("%d\n",-1);
    return 0;
}