日度归档:10 8 月, 2018

洛谷 P1346 电车

基本上是裸的最短路,是第一个不用扳道岔的边长就是0,后面的需要扳道岔的长度就是1。然后愉快的套一个Dijkstra板子就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n,a,b;
struct edge{
    int v,w;
    edge(int vv,int ww){v=vv;w=ww;}
    bool operator < (const edge& e2) const{
        return w>e2.w;
    }
};
vector<edge> edges[105];
priority_queue<edge> pq;
bool visited[105];
int dis[105];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            int v;
            cin>>v;
            if(j==1)edges[i].push_back(edge(v,0));
            else edges[i].push_back(edge(v,1));
        }
    }
    //Dijkstra
    memset(dis,0x7f,sizeof(dis));
    pq.push(edge(a,0));
    while(!pq.empty()){
        edge cur=pq.top();
        pq.pop();
        if(visited[cur.v])continue;
        visited[cur.v]=true;
        dis[cur.v]=cur.w;
        for(int i=0;i<edges[cur.v].size();i++){
            if(!visited[edges[cur.v][i].v]&&dis[edges[cur.v][i].v]>dis[cur.v]+edges[cur.v][i].w){
                dis[edges[cur.v][i].v]=dis[cur.v]+edges[cur.v][i].w;
                pq.push(edge(edges[cur.v][i].v,dis[edges[cur.v][i].v]));
            }
        }
    }
    if(dis[b]!=0x7f7f7f7f)cout<<dis[b];
    else cout<<-1;
}