51Nod 1459 迷宫游戏(Dijkstra+额外松弛第二个权值(分数))

题目大意 ：第一行输入四个数字N(N个顶点)、M(M条弧的信息)、start、end(起点、终点)。第二行输入N个数字，分别代表每个顶点所具有的分数。接下来M行输入弧的信息(顶点1、顶点2、之间的权值w)。问从起点到终点的最小权路径的权值之和以及其对应的最大的分数为多少？

解题思路 ：最短路问题，考虑用Dijkstra，然而题中需要考虑最大分数的这一个条件，我们可以这样想，每次松弛更新时记录前驱结点，这个前驱结点一定是要在相同权值中分数最大的。又发现整个问题其实可以直接记录分数而不考虑前驱结点，所以只要一个maxScore[1…N]记录到的i所得到的分数就行。当然，当i这个顶点还未进入我们的已选取的顶点集时，应保存到达它之前的分数最大和。

AC代码 ：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

#define maxn 505
#define inf 0x3f3f3f3f

typedef long long ll;
typedef long double db;

int Score[maxn],Martix[maxn][maxn];
int n,m,start,end;
int mincost[maxn],vis[maxn],maxScore[maxn];

void Init()
{
    int i,j,x,y,w;
    for(i=0;i<n;i++) {
        scanf("%d",&Score[i]);
    }

    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            if(i==j)
                Martix[i][j]=0;
            else
                Martix[i][j]=inf;
        }
    }

    for(i=0;i<m;i++) {
        scanf("%d%d%d",&x,&y,&w);
        Martix[x][y]=Martix[y][x]=w;
    }

    return ;
}

void Dijkstra()
{
    int u,v,i;

    for(i=0;i<n;i++) {
        mincost[i]=Martix[start][i];
        if(Martix[start][i]!=inf) //到达目前自己的权值
            maxScore[i]=Score[start];
        else
            maxScore[i]=0;
        vis[i]=0;
    }
    vis[start]=1;
    while(1)
    {
        v=-1;
        for(u=0;u<n;u++) {
            if(!vis[u] && (v==-1 || mincost[v]>mincost[u]))
                v=u;
        }
        if(v==-1)
            break;

        vis[v]=1;
        maxScore[v]+=Score[v];

        for(u=0;u<n;u++) {
            if(mincost[u] > mincost[v]+Martix[v][u]) {
                mincost[u]=mincost[v]+Martix[v][u];
                maxScore[u]=maxScore[v];
            }
            else if(mincost[u] == mincost[v]+Martix[v][u] && maxScore[u]<maxScore[v]) {
                maxScore[u]=maxScore[v];
            }
        }
    }

    return ;
}

int main()
{
    int k,i;
    scanf("%d%d%d%d",&n,&m,&start,&end);
    Init();
    Dijkstra();
    printf("%d %d\n",mincost[end],maxScore[end]);
    return 0;
}