记录编号	146201	评测结果	AAPPAAAPPP
题目名称	[AHOI2008] 上学路线	最终得分	60
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	1.378 s
提交时间	2015-01-13 11:21:03	内存使用	25.71 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define Maxn 1010
#define Maxm 524760
#define LL long long
using namespace std;
struct lines{
	int x,y,v,t;
}V[Maxm]={0};
struct edges{
	int y,to,v,id;
	bool sign;
}E[Maxm]={0};
int n,m,tot=1,g[Maxn]={0},S,T,h[Maxn],vh[Maxm],dis[Maxn][Maxn],INF;
void addedge(int x,int y,int v,int id){
	E[++tot].y=y; E[tot].v=v; E[tot].to=g[x]; g[x]=tot; E[tot].id=id; E[tot].sign=1;
	E[++tot].y=x; E[tot].v=0; E[tot].to=g[y]; g[y]=tot; E[tot].id=id; E[tot].sign=0;
}
int dfs(int x,int flow){
	if(x==T) return flow;
	int sum=flow,tmp=h[x]+1;
	for(int i=g[x],p;i;i=E[i].to){
		if(E[i].v&&(h[E[i].y]+1==h[x])){
			p=dfs(E[i].y,min(sum,E[i].v));
			sum-=p; E[i].v-=p; E[i^1].v+=p;
			if(sum==0||h[S]==n) return flow-sum;
		}
	}
	for(int i=g[x];i;i=E[i].to) if(E[i].v) tmp=min(tmp,h[E[i].y]);
	if(--vh[h[x]]==0) h[S]=n; else ++vh[h[x]=tmp+1];
	return flow-sum;
}
int SAP(){
	int maxflow=0;
	memset(h,0,sizeof(h));
	memset(vh,0,sizeof(vh));
	vh[S]=n;
	while(h[S]<n) maxflow+=dfs(S,0x7fffffff);
	return maxflow;
}
void floyed(){
	memset(dis,0x3f,sizeof(dis)); INF=dis[0][0];
	for(int i=1;i<=m;i++){
		dis[V[i].x][V[i].y]=min(dis[V[i].x][V[i].y],V[i].t);
		dis[V[i].y][V[i].x]=min(dis[V[i].y][V[i].x],V[i].t);
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i!=j&&j!=k&&i!=k){
					dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
				}
			}
		}
	}
	for(int i=1;i<=n;i++) dis[i][i]=0; cout<<dis[1][n]<<endl;
}
bool used[Maxn][Maxn]={0};
void rebuild(){
	for(int i=1;i<=m;i++){
		if(used[V[i].x][V[i].y]) continue;
		if(dis[1][V[i].x]<INF&&dis[V[i].y][n]<INF&&dis[1][V[i].x]+dis[V[i].y][n]+V[i].t==dis[1][n]){
			used[V[i].x][V[i].y]=used[V[i].y][V[i].x]=true;
			addedge(V[i].x,V[i].y,V[i].v,i);
			addedge(V[i].y,V[i].x,V[i].v,i);
		}
		else if(dis[1][V[i].y]<INF&&dis[V[i].x][n]<INF&&dis[1][V[i].y]+dis[V[i].x][n]+V[i].t==dis[1][n]){
            used[V[i].x][V[i].y]=used[V[i].y][V[i].x]=true;
			addedge(V[i].x,V[i].y,V[i].v,i);
			addedge(V[i].y,V[i].x,V[i].v,i);
		}
	}
}
bool v[Maxm]={0};
void work(){
	int ans=0,tmp=SAP();
	for(int i=1;i<=tot;i++){
		if(E[i].sign&&E[i].v==0) v[E[i].id]=true;
	}
	for(int i=1;i<=m;i++) if(v[i]) ans++;
	cout<<ans<<' '<<tmp<<endl;
	for(int i=1;i<=m;i++){
		if(v[i]) printf("%d\n",i);
	}
	printf("\n");
}
void init(){
	scanf("%d%d",&n,&m);
	S=1; T=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&V[i].x,&V[i].y,&V[i].t,&V[i].v);
	}
	floyed();
}
int main(){
	freopen("routez.in","r",stdin);
	freopen("routez.out","w",stdout);
	init();
	rebuild();
	work();
	return 0;
}