标签：JSOI2010 旅行 int edge edges 条边 data dp
链接：https://www.luogu.com.cn/problem/P6029
题目描述：给定一个$n$个$m$条边的无向图，可以交换$k$组边，求$1$到$n$的最短路。
题解:发现值域都比较小，考虑$dp$。
我们可以发现，存在一个段点$L$，使得前$L$条边只换不走，后面的$m-L$条边换为前$L$条边，这样走一定不会使答案更差。
令$dp_{i,j,k}$表示到节点$i$，在前$L$条边中选了$j$条边，轮换了$k$次的最短路。
则有:
当前边在前$L$条边时：
$dp_{i,j,k}+edge_{j+1}->dp_{v,j+1,k}$
当前边不在前$L$条边时：
$dp_{i,j,k}+edge_{now}->dp_{v,j,k}$
$dp_{i,j,k}+edge_{j+1}->dp_{v,j,k+1}$
转移可以建分层图跑最短路。
```
#include
#include
#include
using namespace std;
struct node
{
int v,nxt,data;
};
struct edg
{
int u,v,data;
bool operator < (const edg &a)const
{
return data<a.data; }="" };="" struct="" reads="" {="" int="" num,data;="" bool="" operator="" <="" (const="" &a)const="" return="" data="">a.data;
}
};
node edge[2000001];
edg edges[1000001];
int n,m,k,head[1000001],dis[1000001],len;
bool used[1000001];
void add(int x,int y,int z)
{
edge[++len].v=y;
edge[len].data=z;
edge[len].nxt=head[x];
head[x]=len;
return;
}
int d(int x,int y,int z)
{
return (x-1)*(k+1)*(m+1)+y*(m+1)+z+1;
}
reads tmp;
reads make_reads(int x,int y)
{
tmp.num=x;
tmp.data=y;
return tmp;
}
priority_queueq;
void dijkstra()
{
int top;
for (int i=1;i<=d(n,k,m);++i)
{
dis[i]=1e9;
used[i]=0;
}
q.push(make_reads(1,0));
dis[1]=0;
while (!q.empty())
{
top=q.top().num;
q.pop();
if (used[top])
continue;
used[top]=1;
for (int i=head[top];i>0;i=edge[i].nxt)
if (dis[edge[i].v]>dis[top]+edge[i].data)
{
dis[edge[i].v]=dis[top]+edge[i].data;
q.push(make_reads(edge[i].v,dis[edge[i].v]));
}
}
return;
}
int main()
{
int x,y,ans=1e9;
cin>>n>>m>>k;
for (int i=1;i<=m;++i)
cin>>edges[i].u>>edges[i].v>>edges[i].data;
sort(edges+1,edges+m+1);
for (int L=0;L<=m;++L)
{
len=0;
for (int i=1;i<=d(n,k,m);++i)
head[i]=0;
for (int i=1;i<=m;++i)
{
for (int j=0;j<=k;++j)
for (int t=0;t<=L;++t)
{
if (i<=L&&t+1<=L)
{
add(d(edges[i].u,j,t),d(edges[i].v,j,t+1),edges[t+1].data);
add(d(edges[i].v,j,t),d(edges[i].u,j,t+1),edges[t+1].data);
}
else if (i>L)
{
add(d(edges[i].u,j,t),d(edges[i].v,j,t),edges[i].data);
add(d(edges[i].v,j,t),d(edges[i].u,j,t),edges[i].data);
}
}
for (int j=0;j<=k-1;++j)
for (int t=0;t<=L-1;++t)
if (i>L)
{
add(d(edges[i].u,j,t),d(edges[i].v,j+1,t+1),edges[t+1].data);
add(d(edges[i].v,j,t),d(edges[i].u,j+1,t+1),edges[t+1].data);
}
}
dijkstra();
for (int i=0;i<=k;++i)
ans=min(ans,dis[d(n,i,L)]);
}
cout<
标签：JSOI2010,
旅行,
int,
edge,
edges,
条边,
data,
dp
From： https://www.cnblogs.com/zhouhuanyi/p/16983495.html