PAT1003

dijstra算法，自己手敲了一遍。查了半天bug，哭哭。

https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

#include<cstdio>
const int INF = 1e9+7;

int saveNum[505];
int road[505][505];

int dist[505];
int s[505];

int roadSum[505];
int saveSum[505];
/*
dijkstra
*/


void dijstra(int start,int num,int ending)
{
    roadSum[start] = 1;
    saveSum[start] = saveNum[start];
    dist[start] = 0;
    for(int i = 0;i < num;i++)
    {
        int minx = INF,t = 0;
        for(int j = 0;j < num;j++)
        {
            if(dist[j] < minx && !s[j])
            {
                minx = dist[j];
                t = j;
            }
        }
        s[t] = 1;
        for(int k = 0;k < num;k++)
        {
            if(road[t][k] + dist[t]< dist[k] && !s[k])
            {
                dist[k] = road[t][k] + dist[t];
                saveSum[k] = saveSum[t] + saveNum[k];
                roadSum[k] = roadSum[t];
            }
            else if(road[t][k] + dist[t] == dist[k] && !s[k])
            {
                roadSum[k] += roadSum[t];
                if(saveSum[k] < saveSum[t] + saveNum[k])
                    saveSum[k] = saveSum[t] + saveNum[k];
            }
        }
        if(t == ending) break;  // 找到ending点 则停止计算
    }


}

int main()
{
    int cityNum,roadNum,start,ending;
    scanf("%d %d %d %d",&cityNum,&roadNum,&start,&ending);
    for(int i = 0;i < cityNum;i++)
    {
        dist[i] = INF;  // 初始化dist
        for(int j = 0;j < cityNum;j++)  // 初始化road
        {
            if(i == j) road[i][j] = 0;
            else road[i][j] = INF;
        }
    }
    for(int i = 0;i < cityNum;i++)
    {
        scanf("%d",&saveNum[i]);
    }

    for(int i = 0;i < roadNum;i++)
    {
        int x,y,value;
        scanf("%d %d %d",&x,&y,&value);
        road[x][y] = value;
        road[y][x] = value;
        if(x == start)
            dist[y] = value;
        else if(y == start)
            dist[x] = value;
    }

    dijstra(start,cityNum,ending);

    printf("%d %d\n",roadSum[ending],saveSum[ending]);


    return 0;

}