CSP第十二次认证 行车路线 拆点
这道题的关键是如何解决连续小路的情况,因为题目保证答案不超过1e6,说明小路的连续长度不超过1000,给了我们提示,可以将点拆分为两个属性,一个是点的序号,另一个则是最后一段连续小路的长度,所以我们的dist数组dist[i][j]可以表示,从第1个点开始到第i个点,最后一段连续小路的长度为j的疲劳值,这样的话我们就可以同时记录两个我们所需要的值。
ps:dijkstra算法中需要的st判重数组也要拆成两个。
每次更新dist数组需要考虑大路小路两种情况(如下图的两种更新方式),有点类似于动态规划里边的集合的划分,
ps:为了区分两种路我们引入了t数组存储type
最后一条小路的长度不超过1000,同一个点,由于第二维j的不同所以每个点拆成1001个点,我们拆了点之后n相当于500*1001,n是1e5的数据量,m是1e5,所以朴素版的dijkstra和SPFA都会超时,这里我们选择堆优化版的dijkstra。
拆点在CSP目前已经考了三次了,本题是第三次)
拆点:
第一次CCF考试第四题:3200. 无线网络 - AcWing题库
第七次CCF考试第四题:3230. 游戏 - AcWing题库
第十二次CCF考试第四题:AcWing 3255. 行车路线
代码如下:
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 510, M = 1e5 + 10;
int dist[N][1010], h[N], ne[2*M], e[2*M], idx, n, m, t[2*M],w[2*M];
bool st[N][1010];
void add(int type, int a, int b, int c)
{
t[idx] = type;w[idx]=c; e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
struct Node
{
int dis,p,v;
bool operator<(const Node &w)const
{
return dis>w.dis;
}
};
void dij()
{
priority_queue < Node> heap;
//priority_queue默认大根堆,由于Node内置排序为降序,因此还是小根堆
memset(dist, 0x3f, sizeof dist);
heap.push({0,1,0});//dis,p,v
dist[1][0] = 0;
while (heap.size())
{
Node tmp = heap.top();
heap.pop();
register int d=tmp.dis,p=tmp.p;
if (st[p][tmp.v])continue;
st[p][tmp.v]=true;
for (int i = h[p]; i != -1; i = ne[i])
{
register int j = e[i],v=tmp.v;;
if (t[i])
{
v+=w[i];
if(v <= 1000)
{
if (dist[j][v] > d+ v * v-tmp.v*tmp.v)
{
dist[j][v] = d + v * v-tmp.v*tmp.v;
if(dist[j][v] <= 1e6)
heap.push({ dist[j][v],j, v});
}
}
}
else
{
if (dist[j][0] > d + w[i])
{
dist[j][0] = d + w[i];
if(dist[j][0] <= 1e6)
heap.push({ dist[j][0],j,0 });
}
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--)
{
int type, a, b, c;
cin >> type >> a >> b >> c;
add(type, a, b, c);
add(type, b, a, c);
}
dij();
int res = 1e6;
for (int i = 0; i <=100; i++)
res = min(res, dist[n][i]);
cout << res<<endl;
}