Closer's Space

梦河之上, 一叶扁舟

PAT甲级1003最短路


Dijkstra

加一些辅助数组更新即可

代码·

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef  vector<int> VI;
const int maxn = 505;
int dist[maxn][maxn];
bool vis[maxn];
int rescue[maxn]; int mind[maxn];
int maxres[maxn];
int cnt[maxn];

int main() {
  //  freopen("in.txt", "r", stdin);
    int n, m, from, to;
    cin >> n >> m >> from >> to;
    memset(dist, -1, sizeof dist);
    memset(vis, false, sizeof vis);
    memset(cnt, 0, sizeof cnt);
    for(int i = 0; i < n; ++i) cin >> rescue[i];
    while(m--){
        int a, b, v;
        cin >> a >> b >> v;
        dist[a][b] = dist[b][a] = v;
    }
    for(int i = 0; i < n; ++i) {
        mind[i] = i == from ? 0 : dist[from][i];
        maxres[i] = rescue[i];
    }
    cnt[from] = 1;
    for(int i = 1; i < n; ++i){
        int v = 0x7fffffff;
        int u;
        for(int j = 0; j < n; ++j)
            if(!vis[j] && ~mind[j] && mind[j] < v){
                    v = mind[j];
                    u = j;
            }
        vis[u] = 1;
        for(int j = 0; j < n; ++j){
            if(!vis[j] && ~dist[u][j])
                if(mind[j] == -1 || mind[j] > mind[u] + dist[u][j]){
                    mind[j] = mind[u] + dist[u][j];
                    maxres[j] = rescue[j] + maxres[u];
                    cnt[j] = cnt[u];
                }else if(~mind[j] && mind[j] == mind[u] + dist[u][j]){
                    maxres[j] = max(maxres[j], maxres[u] + rescue[j]);
                    cnt[j] += cnt[u];
                }
        }
        if(u == to) break;
    }
    cout << cnt[to] << ' ' << maxres[to] << endl;
    return 0;

博文最后更新时间:


评论

  • Ellalkape
    ellflibre@zmail.website

    Qsymia No Prescription Online Ebay Levitra [url=http://cheapcial40mg.com]cialis[/url] Cialis Wiki

发表评论

来访统计

访问量:116

评论总数:1