PAT 1003 Emergency（求最短路条数 和 第二关键词最大）

题意： n个城镇，给你初始所在城镇和要到达城镇，每个城镇有ai救援队（经过算通知到救援队），问在从起点到达终点 最短路的条数 和 最大通知的救援队人数。

题解： dijsk变形

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <map>using namespace std;const int INF = 0x3f3f3f3f;const int N = 510;const double esp = 1e-3;int mp[N][N],vis[N],dist[N],num[N],need[N];int a[N];int n,m;void init(){    for(int i = 0; i < n; i++)        for(int j = 0; j < n; j++)            if(i == j)  mp[i][j] = 0;            else    mp[i][j] = INF;}void djsk(int begin,int end){    memset(vis,0,sizeof(vis));    memset(need,0,sizeof(need));    memset(num,0,sizeof(num));    for(int i = 0; i < n; i++)        dist[i] = INF;    dist[begin] = 0;    num[begin] = 1;    need[begin] = a[begin];    int MIN,next;    for(int i = 0; i < n; i++)    {        MIN = INF;        for(int j = 0; j < n; j++)        {            if(!vis[j] && dist[j] < MIN)            {                MIN = dist[j];                next = j;            }        }        if(MIN == INF)  break;        vis[next] = 1;        for(int j = 0; j < n; j++)        {            if(!vis[j])            {                if(dist[j] > dist[next]+mp[next][j])                {                    dist[j] = dist[next]+mp[next][j];                    num[j] = num[next];                    need[j] = need[next]+a[j];                }                else if(dist[j] == dist[next]+mp[next][j])                {                    num[j] += num[next];                    need[j] = max(need[j],need[next]+a[j]);                }            }        }    }    PRintf("%d %d/n",num[end],need[end]);}int main(){    int c1,c2;    cin >>n>>m>>c1>>c2;    for(int i = 0; i < n; i++)        cin >> a[i];    init();    while(m--)    {        int x,y,z;        cin >>x>>y>>z;        if(z < mp[x][y])            mp[x][y] = mp[y][x] = z;    }    djsk(c1,c2);    return 0;}