Eva

routeTime Limit: 3 Sec  Memory Limit: 162 MB
Submit: 2804  Solved: 1065
Description

可可和卡卡家住合肥市的东郊，每天上学他们都要转车多次才能到达市区西端的学校。直到有一天他们两人参加了学校的信息学奥林匹克竞赛小组才发现每天上学的乘车路线不一定是最优的。 可可：“很可能我们在上学的路途上浪费了大量的时间，让我们写一个程序来计算上学需要的最少时间吧！” 合肥市一共设有N个公交车站，不妨将它们编号为1…N的自然数，并认为可可和卡卡家住在1号汽车站附近，而他们学校在N号汽车站。市内有M条直达汽车路线，执行第i条路线的公交车往返于站点pi和qi之间，从起点到终点需要花费的时间为ti。(1<=i<=M, 1<=pi, qi<=N) 两个人坐在电脑前，根据上面的信息很快就编程算出了最优的乘车方案。然而可可忽然有了一个鬼点子，他想趁卡卡不备，在卡卡的输入数据中删去一些路线，从而让卡卡的程序得出的答案大于实际的最短时间。而对于每一条路线i事实上都有一个代价ci：删去路线的ci越大卡卡就越容易发现这个玩笑，可可想知道什么样的删除方案可以达到他的目的而让被删除的公交车路线ci之和最小。 [任务] 编写一个程序：  从输入文件中读取合肥市公交路线的信息；  计算出实际上可可和卡卡上学需要花费的最少时间；  帮助可可设计一个方案，删除输入信息中的一些公交路线，使得删除后从家到学校需要的最少时间变大，而被删除路线的ci和最小；向输出文件输出答案。

输入文件中第一行有两个正整数N和M，分别表示合肥市公交车站和公交汽车路线的个数。以下M行，每行（第i行，总第(i+1)行）用四个正整数描述第i条路线：pi, qi, ti, ci；具体含义见上文描述。

输出文件最多有两行。 第一行中仅有一个整数，表示从可可和卡卡家到学校需要的最短时间。 第二行输出一个整数C,表示Ci之和

6 7
1 2 1 3
2 6 1 5
1 3 1 1
3 4 1 1
4 6 1 1
5 6 1 2
1 5 1 4

2
5

2<=N<=500, 1<=M<=124 750, 1<=ti, ci<=10 000
合肥市的公交网络十分发达，你可以认为任意两个车站间都可以通过直达或转车互相到达，当然如果在你提供的删除方案中，家和学校无法互相到达，那么则认为上学需要的最短为正无穷大：这显然是一个合法的方案。

/**************************************************************

    Problem: 1266

    User: ictsing

    Language: C++

    Result: Accepted

    Time:2704 ms

    Memory:10092 kb

****************************************************************/

 

//1266: [AHOI2006]上学路线route

//给定一张图，每条边有一个长度和一个花费，要求删掉一些边使1到n的最短路变长，求最小花销

/*

首先floyd求一发最短路，

然后在最短路中的边都把它们连到图里面去，

注意连接的时候边的权值是哪一个一定要搞清楚，为这个调试半天很划不来23333

然后在这个里面求一个最小割显然就是答案了嘛

*/

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

int g[500+5][500+5];

const int mt=124750+5;

int ecnt=1;

struct edge{

    int x,y,z,w;

}e[mt];

int s,t;

queue<int>q;

int nxt[mt<<2],to[mt<<2],cap[mt<<2];

int adj[500+5],cur[500+5],lev[500+5];

const int inf=0x3f3f3f3f;

void adde(int u,int v,int f)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],cap[ecnt]=f,adj[u]=ecnt;

}

bool bfs()

{

  while(!q.empty()) q.pop();

  for(int i=s;i<=t;i++) lev[i]=-1,cur[i]=adj[i];

  q.push(s),lev[s]=0;

  while(!q.empty())

  {

      int u=q.front();q.pop();

      for(int i=adj[u];i;i=nxt[i])

      {

          int v=to[i];

          if(lev[v]==-1&&cap[i]>0)

            {lev[v]=lev[u]+1,q.push(v);if(v==t) return true;}

      }

  }

  return false;

}

int dinic(int u,int flow)

{

    if(u==t) return flow;

    int res=0,delta;

    for(int &i=cur[u];i;i=nxt[i])

    {

        int v=to[i];

        if(cap[i]>0&&lev[v]>lev[u])

        {

            delta=dinic(v,min(cap[i],flow-res));

            if(delta)

            {

                cap[i]-=delta,cap[i^1]+=delta,res+=delta;

                if(res==flow) break;

            }

        }

    }

    if(res!=flow) lev[u]=-1;

    return res;

}

int mincut()

{

    int ans=0;

    while(bfs()) ans+=dinic(s,inf);

    return ans;

}

inline int read()

{

  int num=0,flag=1;

  char ch;

  do{

    ch=getchar();

    if(ch=='-') flag=-1;

  }while(ch<'0'||ch>'9');

  do{

    num=num*10+ch-'0';

    ch=getchar();

  }while(ch>='0'&&ch<='9');

  return num*flag;

}

int main()

{

    int n=read(),m=read();

    s=1,t=n;

    for(int i=1;i<=n;i++)

       for(int j=1;j<=n;j++)

           {

            g[i][j]=inf;

            if(i==j) g[i][j]=0;

           }

    for(int i=1;i<=m;i++)

    {

       e[i].x=read(),e[i].y=read(),e[i].z=read(),e[i].w=read();

       g[e[i].x][e[i].y]=g[e[i].y][e[i].x]=e[i].z;

    }

    for(int k=1;k<=n;k++)

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

                g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

    printf("%d\n",g[1][n]);

    for(int i=1;i<=m;i++)

    {

        int x=e[i].x,y=e[i].y,z=e[i].z;

        if(g[1][x]+z+g[y][n]==g[1][n])

            adde(x,y,e[i].w),adde(y,x,0);

        if(g[1][y]+z+g[x][n]==g[1][n])//考虑问题是否周全

            adde(y,x,e[i].w),adde(x,y,0);

    }

    printf("%d\n",mincut());

    return 0;

}