1459
双限制最短路
- #include <stdio.h>
- #include <iostream>
- #include <vector>
- #include <math.h>
- #include <algorithm>
- #include <queue>
- #include <string.h>
- #include <set>
- #include <stack>
- #include <stdlib.h>
- #include <time.h>
- using namespace std;
- const int MAX = 0x1f1f1f1f;
- int d[509];
- int g[509][509];
- int v[509];
- int dd[509];
- bool f[509] = {};
- void dji(int n, int s, int e) {
- for(int i=0; i<n; i++) {
- v[i] = g[s][i];
- dd[i] = d[i]+d[s];
- }
- dd[s] -= d[s];
- v[s] = 0;
- f[s] = 1;
- for(int k=1; k<n; ++k) {
- int mi=-1, mmin = MAX, sc = -1;
- for(int j=0; j<n; j++) {
- if(!f[j]) {
- if((v[j] == mmin && dd[j]> sc) || v[j] <mmin) {
- sc = dd[j];
- mmin = v[j];
- mi = j;
- }
- }
- }
- if(mi == -1) break;
- f[mi] = 1;
- for(int i=0; i<n; i++) {
- if(v[i]> mmin + g[mi][i]) {
- v[i] = mmin + g[mi][i];
- dd[i] = sc + d[i];
- } else if(v[i] == mmin + g[mi][i]) {
- dd[i] = max(dd[i], sc + d[i]);
- }
- }
- }
- printf("%d %d\n",v[e], dd[e]);
- }
- int main() {
- int n, m, s, e;
- memset(g, 0x1f, sizeof(g));
- scanf("%d%d%d%d",&n,&m,&s,&e);
- for(int i=0; i<n; i++)
- scanf("%d",&d[i]);
- for(int i=0; i<m; i++) {
- int a,b,c;
- scanf("%d%d%d",&a,&b,&c);
- g[a][b] = g[b][a] = c;
- }
- dji(n,s,e);
- }
来源: http://www.bubuko.com/infodetail-2753818.html