当前位置: 代码迷 >> 综合 >> Travel(dij)
  详细解决方案

Travel(dij)

热度:85   发布时间:2023-12-07 01:26:22.0
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

转自:http://blog.csdn.net/qq_34287501/article/details/78376892

题目描述

精灵王国有N座美丽的城市,它们以一个环形排列在Bzeroth的大陆上。其中第i座城市到第i+1座城市花费的时间为d[i]。特别地,第N座城市到第1座城市花费的时间为d[N]。这些道路都是双向的。

另外,精灵们在数千年的时间里建造了M座传送门,第i座传送门连接了城市u[i]与城市v[i],并且需要花费w[i]的时间通过(可能有两座传送门连接了同一对城市,也有可能一座传送门连接了相同的两座城市)。这些传送门都是双向的。

小S是精灵王国交通部部长,她的职责是为精灵女王设计每年的巡查路线。每次陛下会从某一个城市到达另一个城市,沿路调查每个城市的治理情况,


她需要找出一条用时最短的路线。

输入描述:

第一行为2个整数N、M。
第二行为N个正整数d[i]。
接下来M行每行三个正整数u[i]、v[i]、w[i]。
第M+3行为一个正整数Q,表示需要设计路线的次数。
接下来Q行每行两个正整数x、y,表示一次从城市x到城市y的旅行。

输出描述:

Q行每行一个正整数表示该次旅行的最短时间。
示例1

输入

4 1
1 2 3 6
1 3 2
5
1 2
1 4
1 3
2 3
4 3

输出

1
5
2
2
3

备注:

1 ≤ N、Q ≤ 52501,1 ≤ M ≤ 20,1 ≤ u[i]、v[i]、x、y ≤ N,1 ≤ d[i]、w[i] ≤ 2^(30) 
解析:该图是一个环,再加上一些传送门(就是一些边),要想求最短距离,必然从两方面考虑,没有经过传送门和经过传送门,咱可以把所有有关传送门的点,暴力求下到所有点的最短距离,因为传送点数少,最多40个,暴力下就是40*n*log(n),然后每次询问的复杂度为O(1),就是遍历下传送门的40个点,这样就可以写了,不会超时了
  
   
#include<bits/stdc++.h>
using namespace std;
typedef  long long LL;
LL d[ 60001 ], dis[ 41 ][ 60001 ], sum[ 60001 ];
int id[ 41 ], n;
struct node
{
     int v;
     LL w;
};
//dis[第几个有传送门的城市][其他城市编号]=到其他城市的最短距离
vector<node> mp[ 60001 ];
typedef pair< int , LL> P;
vector< int > vx;
void dij( int s)   //有传送门的城市在数组的位置
{
     for ( int i =  1 ; i <= n; i++) dis[s][i] = 1ll<< 60 ;
     dis[s][id[s]] =  0 ;
     priority_queue<P, vector<P>, greater<P> > q;//优先队列
     q.push(make_pair(id[s],  0 ));
     while (!q.empty())
     {
         P p = q.top(); q.pop();
         int v = p.first;
         if (dis[s][v] < p.second)  continue ;
         for ( int i =  0 ; i < mp[v].size(); i++)
         {
             node e = mp[v][i];
             if (dis[s][e.v] > dis[s][v] + e.w)
             {
                 dis[s][e.v] = dis[s][v] + e.w;
                 q.push(make_pair(e.v, dis[s][e.v]));
             }
         }
     }
}//迪杰斯特拉算法
int main()
{
     int m;
     LL res =  0 ;
     scanf( "%d%d" , &n, &m);
     for ( int i =  1 ; i <= n; i++)
     {
         scanf( "%I64d" , &d[i]);
         res += d[i];
         //求总距离 下面的1-n的距离会用到
         mp[i].push_back((node){i%n+ 1 , d[i]});
         mp[i%n+ 1 ].push_back((node){i, d[i]});
         //这个地方是把从i到相邻的两座城市的距离存起来了
         //i是城市编号 i%n+1是城市编号 d[i]是两城市间距离 双向 且1与n的距离为d[n]
     }
     sum[ 1 ] =  0 ;
     for ( int i =  2 ; i <= n; i++) sum[i] = sum[i- 1 ] + d[i- 1 ];
     //所有的城市到第一个城市的距离
     int u, v, w;
     for ( int i =  1 ; i <= m; i++)
     {
         scanf( "%d%d%d" , &u, &v, &w);
         node cur;
         cur.v = v;
         cur.w = w;
         mp[u].push_back(cur);
         cur.v = u;
         mp[v].push_back(cur);
     //存入之前所存的两城市距离、双向
         vx.push_back(u); vx.push_back(v);
     //有传送门的城市编号入队列
     }
     LL len = unique(vx.begin(), vx.end()) - vx.begin();
     //统计有多少个有传送门的城市
     for (LL i =  1 ; i <= len; i++)
     {
         id[i] = vx[i- 1 ];
         //有传送门的城市编号存入数组
         dij(i);
         //求出有传送门的城市与其他所有城市的最短距离
     }
     int q;
     scanf( "%d" , &q);
     while (q--)
     {
         scanf( "%d%d" , &u, &v);
         LL ans = abs(sum[v] - sum[u]);
         //两个城市间不经过传送门的距离
         ans = min(ans, res - ans);
         //一个城市到另一个城市不经过传送门的两个方向的距离 取小的
         for ( int i =  1 ; i <= len; i++)
         {
             ans = min(ans, dis[i][u] + dis[i][v]);
             //与经过传送门的距离比较 取小的
         }
         printf( "%lld\n" , ans);
     }
     return 0 ;
}
求图的最短路径算法(四种)可参考:http://blog.csdn.net/qibofang/article/details/51594673
大神讲解非常详细了。