Dijkstra | 1003 Emergency （25 po

本来想先拣20分题先刷，然鹅考虑到之后一直刷25/30分题半天过不了可能会自闭，还是按顺序刷吧emmmm

1003 Emergency

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define N 510
const int INF=0x3f3f3f3f;
int n,m,from,to;
int graph[N][N];
int dist[N],teams[N];
int path_cnt[N];
int team_cnt[N];
bool done[N];

void dijkstra(){
    dist[from]=0;
    path_cnt[from]=1;
    team_cnt[from]=teams[from];
    int cnt_done=0;
    while(cnt_done<n) {
        int curr=INF,min=INF;
        for (int i = 0; i < n; ++i) {
            if(!done[i]&&dist[i]<min) {
                curr = i;
                min=dist[i];
            }
        }
        if(curr==INF) {
            break;
        }
        done[curr]= true;
        for (int i=0;i<n;++i) {
            int new_dist=dist[curr]+graph[curr][i];
            if(new_dist<dist[i]){
                dist[i]=new_dist;
                path_cnt[i]=path_cnt[curr];
                team_cnt[i]=team_cnt[curr]+teams[i];
            } else if(new_dist==dist[i]){
                path_cnt[i]+=path_cnt[curr];
                if(team_cnt[curr]+teams[i]>team_cnt[i]){
                    team_cnt[i]=team_cnt[curr]+teams[i];
                }
            }
        }
        cnt_done++;
    }
}

int main() {
    scanf("%d%d%d%d",&n,&m,&from,&to);
    for (int i = 0; i < n; ++i) {
        scanf("%d",&teams[i]);
        for (int j = 0;j < n;j++)
            graph[i][j]=INF;
    }
    int u,v,w;
    for (int i = 0; i < m; ++i) {
        scanf("%d%d%d",&u,&v,&w);
        if(w<graph[u][v]) {
            graph[u][v] = w;
            graph[v][u] = w;
        }
    }
    if(from==to) {
        printf("1 %d\n", teams[to]);
        return 0;
    }
    memset(done, false, sizeof(done));
    memset(dist,INF, sizeof(dist));
    memset(path_cnt,0, sizeof(path_cnt));
    dijkstra();
    printf("%d %d\n",path_cnt[to],team_cnt[to]);
    return 0;
}

更多：
柳婼 最短路径
memset和fill