[JSOI2010] 旅行
给定一张无向图,可以k次交换两条边边权，求1到n的最短路
交换执行于求最短路之前，边权1<=c<=1000
点数<=50
边数<=150
k<=20
此题找不到题解求神犇留言做法
我的想法。。。先求从1-n，无视i条边边权的最短路，然后在路径外找i条最短的加回去。。
最后只对了5个点。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include<cmath> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pa pair<int,int> #define inf 1000000000 #define eps 1e-8 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int mn; int head,tail; int n,m,K,cnt=1; int d[55][25],p[55][25],f[55][25]; int x[10005],y[10005]; bool vis[55][25],mark[305]; int last[55]; priority_queue<int,vector<int>,greater<int> >q; struct edge{ int from,to,next,v; }e[305]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].from=u;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; e[++cnt].to=u;e[cnt].from=v;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w; } void push(int nx,int ny) { if(!vis[nx][ny]) { vis[nx][ny]=1; x[tail]=nx;y[tail]=ny;tail++; if(tail==10005)tail=0; } } void spfa() { tail=1;x[0]=1; while(head!=tail) { int nx=x[head],ny=y[head];head++; if(head==10005)head=0; vis[nx][ny]=0; for(int i=last[nx];i;i=e[i].next) { if(d[nx][ny]+e[i].v<d[e[i].to][ny]) { d[e[i].to][ny]=d[nx][ny]+e[i].v; p[e[i].to][ny]=i;f[e[i].to][ny]=1; push(e[i].to,ny); } if(ny<K&&d[nx][ny]<d[e[i].to][ny+1]) { d[e[i].to][ny+1]=d[nx][ny]; p[e[i].to][ny+1]=i;f[e[i].to][ny+1]=0; push(e[i].to,ny+1); } } } } void solve(int x) { while(!q.empty())q.pop(); int nx=n,ny=x,ans=d[n][x]; memset(mark,0,sizeof(mark)); while(nx!=1) { int ed=p[nx][ny],flag=f[nx][ny]; mark[ed]=flag; ny-=(flag==0); nx=e[ed].from; } for(int i=2;i<=cnt;i+=2) if(!mark[i]&&!mark[i^1])q.push(e[i].v); while(x--) ans+=q.top(),q.pop(); mn=min(mn,ans); } int main() { n=read();m=read();K=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } memset(d,127/3,sizeof(d)); d[1][0]=0; spfa(); mn=inf; for(int i=0;i<=K;i++) solve(i); printf("%d\n",mn); return 0; } |
计数器 9527629
OI 课件=>
OI 课件=>
一定是选一条路径，将大的边换成小的。但是不能直接取前K小，有可能会交换到已经在路径上的边。
注意到已经在路径上的边加上交换的边一定是排序后边的一个前缀，所以可以枚举这个前缀，然后求出dis[u][i][j]表示从1到u，经过i条已经在前缀的边，替换了j条边，这种情况的最短路（不包含这i+j条边），用dis[N][i][j]+w[1..i+j]更新答案（i+j小于前缀长度时可能会不合法，所以只能用i+j等于前缀长度的更新答案）。
有一个问题是可能存在边权相同的边，排序上可能会有一点问题，我的做法是枚举边权，然后前缀长度就是一个范围。
大神，我为什么在bzoj上找不到这道题？