2021/08/22 15:04
思路:dfs,dijkstra
给定n条地铁线路经停站,再给出m个询问,每个询问包含两个站点,求出两个站点的最短途径站,如果有多条,则选择换乘次数最少的,依次输出途径站数,及路径经过每条地铁路线的起点和终点
DFS
一开始我的想法是用邻接矩阵依次存下相邻两个站点的线路编号,然后邻接表存图,dfs一遍即可
但是这里的站点编号是1e5
的,开邻接矩阵存不下来,会报内存超限
然后柳神提供了一个很好的思路,用unordered_map
去存,第一维存id1 * 1e5 + id2
, 第二维存线路编号 ,表示id1
能去id2
这样不就可以为所欲为,直接dfs
,过程中维护路径和换乘次数和上一个点
如果此时已经找到了路径,当前的路径已经大于之前的答案路径,直接return
如果当前的路径长度等于之前的答案路径,并且换乘次数大于之前的答案换乘次数,直接return
(发现数据bug,我同时维护了最短路径和最小换乘次数,也就是说一旦找到一条路径,下一条路径更新的的条件是路径长度更小换乘次数也更小 这样与求最短路径相违背 这样能过acwing,pta官网只能得1/3分数 已提交工单)
最后得到了path[]
,双指针去维护一条地铁线路的站点
转化为dijkstra
为同一条地铁线的站点都建立一条边,边权为途径站点数(注意地铁线为回路时,需要取顺时针和逆时针的最小值)
这样问题就转化成了求单源最短路径同时使得所经点最小
由于这里点数比较多(1e5
),所以用堆优化的dijkstra,需要维护dist[], cnt[], pre[], info[]
dist[]表示从起点到该点的最短距离, cnt[]表示从起点到该点所经过的点数, pre[]表示路径的前一个点, info[]表示到达该点时需要输出的线路乘坐信息
优先考虑dist, dist相同再看cnt
DFS代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 1e5;
bool vis[N + 10];
int n, m, x, p, cnt, start, target;
vector<int> G[N + 10], path, tpath;
unordered_map<int, int> line;
void dfs(int u, int pre, int tcnt)
{
if(cnt != N && tpath.size() > path.size())
return ;
if(tpath.size() == path.size() && tcnt > cnt)
return ;
if(u == target)
{
path = tpath;
cnt = tcnt;
return ;
}
for (int i = 0; i < G[u].size(); i ++ )
{
int t = G[u][i];
if(!vis[t])
{
tpath.push_back(t);
vis[t] = true;
int x = line[pre * N + u] != line[u * N + t] ? 1 : 0;
dfs(t, u, tcnt + x);
vis[t] = false;
tpath.pop_back();
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> m >> p;
for (int j = 0; j < m - 1; j ++ )
{
cin >> x;
G[p].push_back(x), G[x].push_back(p);
line[p * N + x] = line[x * N + p] = i;
p = x;
}
}
cin >> m;
while (m -- )
{
cin >> start >> target;
tpath.clear(), path.clear();
cnt = N, tpath.push_back(start);
memset(vis, 0, sizeof vis);
vis[start] = true;
dfs(start, -1, 0);
cout << path.size() - 1 << endl;
for(int i = 0; i + 1 < path.size(); i++)
{
int j = i + 1, line_id = line[path[i] * N + path[i + 1]];
while(j + 1 < path.size() && line_id == line[path[j] * N + path[j + 1]])
j++;
printf("Take Line#%d from %04d to %04d.\n", line_id, path[i], path[j]);
i = j - 1;
}
}
return 0;
}
dijkstra代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 1e6 + 10;
bool vis[N];
int n, m, k, x;
string info[N];
int dist[N], cnt[N], pre[N];
int h[N], e[M], ne[M], w[M], line[M], idx;
string get_number(int num)
{
string s = to_string(num);
while(s.size() < 4)
s = "0" + s;
return s;
}
void add(int a, int b, int len, int id)
{
e[idx] = b;
w[idx] = len;
line[idx] = id;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra(int s, int x)
{
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
memset(cnt, 0, sizeof cnt);
dist[s] = 0;
priority_queue<PII, vector<PII>, greater<PII>> q;
q.push({0, s});
while(q.size())
{
auto t = q.top();
q.pop();
int ver = t.second, d = t.first;
if(vis[ver])
continue;
if(ver == x)
break;
vis[ver] = true;
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if(dist[j] > d + w[i])
{
dist[j] = d + w[i];
pre[j] = ver;
cnt[j] = cnt[ver] + 1;
info[j] = "Take Line#" + to_string(line[i]) +
" from " + get_number(ver) + " to " +
get_number(j) + ".";
q.push({dist[j], j});
}
else if(dist[j] == d + w[i])
{
if(cnt[j] > cnt[ver] + 1)
{
pre[j] = ver;
cnt[j] = cnt[ver] + 1;
info[j] = "Take Line#" + to_string(line[i]) +
" from " + get_number(ver) + " to " +
get_number(j) + ".";
}
}
}
}
cout << dist[x] << endl;
vector<string> ans;
for(int i = x; i != s; i = pre[i])
ans.push_back(info[i]);
reverse(ans.begin(), ans.end());
for(auto &s : ans)
cout << s << endl;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> m;
vector<int> path(m);
for (int j = 0; j < m; j ++ )
cin >> path[j];
for (int j = 0; j < m; j ++ )
{
for (int k = 0; k < j; k ++ )
{
int len = j - k;
if(path[0] == path[m - 1])
len = min(len, m - len - 1);
add(path[j], path[k], len, i);
add(path[k], path[j], len, i);
}
}
}
cin >> k;
while(k--)
{
int a, b;
cin >> a >> b;
dijkstra(a, b);
}
return 0;
}
想问下这dfs代码时间复杂度怎么算