记录编号	322650	评测结果	AAAAAAAAAA
题目名称	[AHOI2008] 上学路线	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.248 s
提交时间	2016-10-15 13:55:00	内存使用	14.42 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
#define Mem(a,v) memset(a,v,sizeof(a))
using namespace std;
/*
freopen(".in","r",stdin);
	freopen(".out","w",stdout);
getchar(); getchar();
	return 0;
*/
const int inf = 0x7f7f7f7f;
#define maxn 510
#define maxe 124750<<1
int N,M,len,head[maxn],L;
struct Edge
{
	int s,to,dis,next,num,c; 	
}a[maxe];

void insert(int x,int y,int z,int c,int i){
	a[++len].to = y; a[len].s = x; a[len].dis = z;
	a[len].num = i;	a[len].c = c;
	a[len].next = head[x]; head[x] = len;
}
void Read(){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++){
		int x,y,z,c;scanf("%d%d%d%d",&x,&y,&z,&c);
		insert(x,y,z,c,i); insert(y,x,z,c,i);
	}	
}
bool f[maxn];
int dis[maxn];
deque <int> q;
void The_Shortest_roads(){
	while(!q.empty())q.pop_back();
	Mem(dis,63); dis[1] = 0;
	//SPFA_SLF
	q.push_back(1); f[1] = 1;
	while(!q.empty()){
		int k = q.front(); q.pop_front();
		f[k] = 0;
		for(int i=head[k];i;i=a[i].next){
			int p = a[i].to;
			if(dis[p] > dis[k]+a[i].dis){
				dis[p] = dis[k]+a[i].dis;
				if(!f[p]){
					f[p] = 1;
					if(!q.empty() && dis[q.front()] > dis[p]){
						q.push_front(p);	
					} else {
						q.push_back(p);	
					}
				}	
			}	
		}	
	}
	printf("%d\n",dis[N]);
	/*
	for(int i=1;i<=N;i++){
		printf("dis = %d\n",dis[i]);	
	}*/
}
struct Dinic_Edge
{
	int to,flow,next,num,cap;
}e[maxe*2];
void Add_Edge(int x,int y,int cap,int i){
	e[L].to = y; e[L].num = i; e[L].flow = e[L].cap = cap;
	e[L].next = head[x]; head[x] = L++;
}
void Re_Build_Edge(){
	Mem(head,-1); L = 0;
	for(int i=1;i<=len;i++){
		int x = a[i].s , y = a[i].to;
		if(dis[x]+a[i].dis == dis[y]){//在最短路中 
			int cap = a[i].c , num = a[i].num;
			Add_Edge(x,y,cap,num);
			Add_Edge(y,x,0,num);
		}
	}
}
int qu[maxn],h,r,dep[maxn];
bool BFS(){
	Mem(dep,-1); h = r = 0;
	qu[r++] = 1; dep[1] = 0;
	while(h != r){
		int k = qu[h++];
		for(int i=head[k];i!=-1;i=e[i].next){
			int p = e[i].to;
			if(dep[p] < 0 && e[i].flow > 0){
				dep[p] = dep[k] + 1;
				qu[r++] = p;	
			}
		}	
	}	
	if(dep[N] > 0) return 1;
	else return 0;
}
int DFS(int x,int Low){
	if(x==N || !Low) return Low;
	int flow=0,f=0;
	for(int i=head[x];i!=-1;i=e[i].next){
		int p = e[i].to;
		if(dep[p]==dep[x]+1){
			f = DFS(p,min(Low,e[i].flow));
			if(!f) continue;
			flow += f; Low -= f;
			e[i].flow -= f; e[i^1].flow += f;
			if(!Low) break;	
		}	
	}	
	return flow;
}
int ans=0;
void Dinic(){
	while( BFS() ){
		ans += DFS(1,inf);
	}
//	printf("%d\n",ans);
}
bool ufs[maxe*2];
void Check(){
	int cnt=0;
	for(int i=0;i<L;i+=2){
		if(!e[i].flow){
//			printf("num = %d\n",e[i].num);
			cnt ++ ; ufs[i] = 1;
		}
	}	
	printf("%d %d\n",cnt,ans);
	for(int i=0;i<L;i+=2){
		if(ufs[i]){
			printf("%d\n",e[i].num);	
		}	
	}
}
int main(){
	freopen("routez.in","r",stdin);
	freopen("routez.out","w",stdout);
	Read();
	The_Shortest_roads();
	Re_Build_Edge();
	Dinic();
	Check();
//	getchar(); getchar();
	return 0;
}