学步园

题目链接：点击打开链接

pay与dis一起进行更新。

代码：

#include<cstdio>
#include<cstring>
#define INF 0xffffff

const int N=1005;
int Map[N][N],pMap[N][N];
int dis[N],pay[N];
bool vis[N];
int n,m;

void Init()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    {Map[i][j]=INF;pMap[i][j]=INF;}
}

void Dijkstra(int u0)
{
    memset(vis,0,sizeof(vis));
    vis[u0]=true;
    for(int i=1;i<=n;i++)
    {dis[i]=Map[u0][i];pay[i]=pMap[u0][i];}
    dis[u0]=0;pay[u0]=0;
//    for(int k=1;k<=n;k++)
//    printf("(%d %d)\n",dis[k],pay[k]);
    for(int i=1;i<=n;i++)
    {
        int temp=INF,ptemp=INF,t=u0;
        for(int j=1;j<=n;j++)
        if(!vis[j])
        {
            if(temp>dis[j])
            {temp=dis[j];ptemp=pay[j];t=j;}
            else if(temp==dis[j]&&ptemp>pay[j])
            {temp=dis[j];ptemp=pay[j];t=j;}
        }
        if(t==u0) return;
        vis[t]=true;
        for(int j=1;j<=n;j++)
        if(!vis[j])
        {
            if(dis[j]>dis[t]+Map[t][j])
            {dis[j]=dis[t]+Map[t][j];pay[j]=pay[t]+pMap[t][j];}
            else if(dis[j]==dis[t]+Map[t][j]&&pay[j]>pay[t]+pMap[t][j])
            {dis[j]=dis[t]+Map[t][j];pay[j]=pay[t]+pMap[t][j];}
        }
    }
}

int main()
{
    while(scanf("%d%d",&n,&m)&&(n+m))
    {
        Init();
        for(int i=1;i<=m;i++)
        {
            int a,b,d,p;
            scanf("%d%d%d%d",&a,&b,&d,&p);
            if(d<Map[a][b])
            {
                Map[a][b]=d;Map[b][a]=d;
                pMap[a][b]=p;pMap[b][a]=p;
            }
            else if(d==Map[a][b]&&p<pMap[a][b])
            {
                Map[a][b]=d;Map[b][a]=d;
                pMap[a][b]=p;pMap[b][a]=p;
            }
        }
        int s,t;
        scanf("%d%d",&s,&t);
        Dijkstra(s);
//        for(int k=1;k<=n;k++)
//        printf("%d %d\n",dis[k],pay[k]);
        printf("%d %d\n",dis[t],pay[t]);
    }
    return 0;
}