终于不是网络流了= =

BZOJ2763/2662

题意都差不多，代码都只差一点= =：都是在一个无向图中，你一共有k次改变一条边上的权值的机会，求最短路= =（两道题在细节上有一点区别= =）

做法：拆成k个点，然后再跑最短路= =，貌似叫做分层图。

2763：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 100050
#define INF 0x7f7f7f7f
struct Point
 {
 	int a1,a2;
 };
queue <Point> a;
int fi[N],c[M][3],h[N][20],n,m,v,S,T,ss=0;
bool b[N][20];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar();while (y<'0'||y>'9');
 	do x=(x << 3)+(x << 1)+y-'0',y=getchar();
 	   while (y>='0'&&y<='9');
 	return x;
 }
inline void Line (int x,int y,int z)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
 	return;
 }
int main()
 {
 	int i,j,q,w,e;
 	Point k,l;
 	memset(c,0,sizeof(c));memset(h,0,sizeof(h));
 	memset(fi,0,sizeof(fi));memset(b,0,sizeof(b));
 	scanf("%d%d%d%d%d",&n,&m,&v,&S,&T);
 	for (i=1;i<=m;i++)
 	  q=Read(),w=Read(),e=Read(),Line(q,w,e);
 	for (i=0;i<n;i++)
 	 for (j=0;j<=v;j++)
 	   h[i][j]=INF;
 	h[S][0]=0;k.a1=S;k.a2=0;a.push(k);b[S][0]=1;
 	while (!a.empty())
 	 {
 	 	k=a.front();
 	 	for (i=fi[k.a1];i;i=c[i][1])
 	 	 {
 	 	 	if (h[c[i][0]][k.a2]>c[i][2]+h[k.a1][k.a2])
 	 	 	 {
 	 	 	 	h[c[i][0]][k.a2]=c[i][2]+h[k.a1][k.a2];
 	 	 	 	if (!b[c[i][0]][k.a2])
 	 	 	 	  b[c[i][0]][k.a2]=1,l=k,l.a1=c[i][0],
 	 	 	 	  a.push(l);
 	 	 	 }
 	 	 	if (k.a2<v&&h[c[i][0]][k.a2+1]
 	 	 		 >h[k.a1][k.a2])
 	 	 	 {
 	 	 	 	h[c[i][0]][k.a2+1]=h[k.a1][k.a2];
 	 	 	 	if (!b[c[i][0]][k.a2+1])
 	 	 	 	  b[c[i][0]][k.a2+1]=1,l=k,l.a1=c[i][0],l.a2++,
 	 	 	 	  a.push(l);
 	 	 	 }
 	 	 }
 	 	a.pop();b[k.a1][k.a2]=0;
 	 }
 	e=INF;
 	for (i=0;i<=v;i++)
 	  e=min(e,h[T][i]);
 	printf("%d\n",e);
 	return 0;
 }

2662：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 10050
#define M 100050
#define INF 0x7f7f7f7f
struct Point
 {
 	int a1,a2;
 };
queue <Point> a;
int fi[N],c[M][3],h[N][20],n,m,v,S,T,ss=0;
bool b[N][20];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar();while (y<'0'||y>'9');
 	do x=(x << 3)+(x << 1)+y-'0',y=getchar();
 	   while (y>='0'&&y<='9');
 	return x;
 }
inline void Line (int x,int y,int z)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=z;fi[y]=ss;
 	return;
 }
int main()
 {
 	int i,j,q,w,e;
 	Point k,l;
 	memset(c,0,sizeof(c));memset(h,0,sizeof(h));
 	memset(fi,0,sizeof(fi));memset(b,0,sizeof(b));
 	scanf("%d%d%d",&n,&m,&v);S=1;T=n;
 	for (i=1;i<=m;i++)
 	  q=Read(),w=Read(),e=Read(),Line(q,w,e);
 	for (i=1;i<=n;i++)
 	 for (j=0;j<=v;j++)
 	   h[i][j]=INF;
 	h[S][0]=0;k.a1=S;k.a2=0;a.push(k);b[S][0]=1;
 	while (!a.empty())
 	 {
 	 	k=a.front();
 	 	for (i=fi[k.a1];i;i=c[i][1])
 	 	 {
 	 	 	if (h[c[i][0]][k.a2]>c[i][2]+h[k.a1][k.a2])
 	 	 	 {
 	 	 	 	h[c[i][0]][k.a2]=c[i][2]+h[k.a1][k.a2];
 	 	 	 	if (!b[c[i][0]][k.a2])
 	 	 	 	  b[c[i][0]][k.a2]=1,l=k,l.a1=c[i][0],
 	 	 	 	  a.push(l);
 	 	 	 }
 	 	 	if (k.a2<v&&h[c[i][0]][k.a2+1]
 	 	 		 >h[k.a1][k.a2]+c[i][2]/2)
 	 	 	 {
 	 	 	 	h[c[i][0]][k.a2+1]=h[k.a1][k.a2]+c[i][2]/2;
 	 	 	 	if (!b[c[i][0]][k.a2+1])
 	 	 	 	  b[c[i][0]][k.a2+1]=1,l=k,l.a1=c[i][0],l.a2++,
 	 	 	 	  a.push(l);
 	 	 	 }
 	 	 }
 	 	a.pop();b[k.a1][k.a2]=0;
 	 }
 	e=INF;
 	for (i=0;i<=v;i++)
 	  e=min(e,h[T][i]);
 	printf("%d\n",e);
 	return 0;
 }