hdu 3790

3 21 2 5 62 3 4 51 30 0Sample Output
9 11
#include<stdio.h>#include<algorithm>#include<string.h>using namespace std;int dis[100003][2];int maps[1003][1003][2];int x,y;int n,m;int vis[100003];void dijkstra(){    memset(vis,0,sizeof(vis));    for(int i=1; i<=n; i++)    {        dis[i][0]=maps[x][i][0];        dis[i][1]=maps[x][i][1];    }    vis[x]=1;    for(int i=1; i<n; i++)    {        int p;        int m_min=0x1f1f1f1f;        for(int j=1; j<=n; j++)        {            if(m_min>dis[j][0]&&!vis[j])            {                m_min=dis[j][0];                p=j;            }        }        vis[p]=1;        for(int j=1; j<=n; j++)        {            if(dis[j][0]>dis[p][0]+maps[p][j][0])            {                dis[j][0]=dis[p][0]+maps[p][j][0];                dis[j][1]=dis[p][1]+maps[p][j][1];            }            if(dis[j][0]==dis[p][0]+maps[p][j][0])            {                dis[j][1]=min(dis[j][1],dis[p][1]+maps[p][j][1]);            }        }    }}int main(){    while(scanf("%d%d",&n,&m)==2&&(n||m))    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)            {                if(i==j)                    maps[i][j][0]=0,maps[i][j][0]=0;                else maps[i][j][1]=maps[i][j][0]=0x1f1f1f;            }        }        for(int i=0; i<m; i++)        {            int a,b,c,d;            scanf("%d%d%d%d",&a,&b,&c,&d);            if(maps[a][b][0]>c||(maps[a][b][0]==c&&maps[a][b][1]>d))            {                maps[a][b][0]=maps[b][a][0]=c;                maps[a][b][1]=maps[b][a][1]=d;            }        }        scanf("%d%d",&x,&y);        dijkstra();        PRintf("%d %d/n",dis[y][0],dis[y][1]);    }}