HDU 3790 最短路问题（最短路）

【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=3790

题目意思

如题，就多问了个花费而已

解题思路

创个结构体跑模板就可以了

代码部分

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=;
const int INF=;
int n,m,s,t;
struct note
{
    int d;
    int p;
} a[maxn][maxn];
int vis[maxn],dis[maxn],pr[maxn];
void dist ()
{
    dis[s]=;
    pr[s]=;
    int j=s;
    for (int i=; i<=n; i++)
    {
        s=j;
        vis[j]=;
        //cout<<j<<endl;
        if (j==t)
        {
            printf("%d %d\n",dis[t],pr[t]);
            return ;
        }
        for (int k=; k<=n; k++)
        {
            if (!vis[k])
            {
                if (dis[s]+a[s][k].d<dis[k])
                {
                    dis[k]=dis[s]+a[s][k].d;
                    pr[k]=pr[s]+a[s][k].p;
                }
                else if(dis[s]+a[s][k].d==dis[k])
                {
                    pr[k]=min(pr[s]+a[s][k].p,pr[k]);
                }
            }
        }
        int mi=INF,mip=INF;
        for (int k=; k<=n; k++)
        {
            if (!vis[k]&&(mi>dis[k]||(dis[k]==mi&&pr[k]<mip)))
            {
                j=k;
                mi=dis[k];
                mip=pr[k];
            }
        }
    }
}
int main()
{
    while (scanf("%d %d",&n,&m),m!=&&n!=)
    {
        memset(vis,,sizeof(vis));
        memset(dis,INF,sizeof(dis));
        memset(pr,INF,sizeof(pr));
        for (int i=; i<=n; i++)
            for (int j=; j<=n; j++)
            {
                a[i][j].d=INF;
                a[i][j].p=INF;
            }
        for (int i=; i<m; i++)
        {
            int x,y,p1,d1;
            scanf("%d %d %d %d",&x,&y,&d1,&p1);
            if (d1<a[x][y].d||(d1==a[x][y].d&&p1<a[x][y].p))
            {
                a[x][y].d=d1;
                a[x][y].p=p1;
                a[y][x].d=d1;
                a[y][x].p=p1;
            }
        }
        scanf("%d %d",&s,&t);
        dist();
    }
}