图论 - Travel-白红宇

图论 - Travel

阅读量：6280 次

发布时间：2019-06-22

本文共 1686 字，大约阅读时间需要 5 分钟。

Travel

The country frog lives in has nn towns which are conveniently numbered by 1,2,…,n.

Among n(n−1) / 2 pairs of towns, m of them are connected by bidirectional highway, which needs aa minutes to travel.

The other pairs are connected by railway, which needs bb minutes to travel.

Find the minimum time to travel from town 1 to town n.

Input

The input consists of multiple tests. For each test:

The first line contains 4 integers n,m,a,bn,m,a,b (2≤n≤1e5,0≤m≤5⋅1e5,1≤a,b≤1e9).

Each of the following mm lines contains 22 integers ui,viui,vi, which denotes cities uiui and vivi are connected by highway. (1≤ui,vi≤n,ui≠vi).

Output

For each test, write 1 integer which denotes the minimum time.

Sample Input

3 2 1 3

1 2

2 3

3 2 2 3

1 2

2 3

Sample Output

-----------------------------------------我是分割线^_^--------------------------------- 这个题就是一个求补图的最短路的很好的例子，由于在这个题中补图的权值一样，所以就可以和用 BFS求普通的最短路一样的求解了，至于结构体的方式来储存邻接表还是第一次，不过感觉挺方便的 所以以后还是尽量习惯吧，对了，还要注意理解题解中set的作用，用来筛选出与当前点未连接的点。

#include
    
     #include
     
      #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
               #include
               
                 using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define INF 0x3f3f3f3f #define Int __int64 #define pii pair
                
                  #define check(x) cout<<"["<
                 
                  <<"]"<

q; while (!q.empty()) q.pop(); vis[1] = true; q.push(1); while (!q.empty()) { int now = q.front(); q.pop(); for (int i = head[now]; i != -1; i = edge[i].nxt) { int v = edge[i].v; int w = edge[i].w; if (dis[v] > dis[now] + w) { dis[v] = dis[now] + w; if (!vis[v]) {//标记这里还是有点疑问，因为有的人不标记也行= = vis[v] = true; q.

转载于:https://www.cnblogs.com/steamedbun/p/5786710.html

你可能感兴趣的文章