记录一个菜逼的成长。。
题目大意： 给你N个城市，M条路。给你初始点s和终止点t。 问从s到t的最短路径数和最大救援队数。
用cnt[i] := 表示在最短路的条件下，从s到达i点的最短路径数 如果在从s到i的路径中有一点j使得dis[i] == dis[j] + g[i][j],则cnt[i] += cnt[j]; 如果dis[i] > dis[j] + g[i][j];则cnt[i] = cnt[j];
用val[i] := 表示在最短路条件下，从s到达i点的最大救援队数。 如果在从s到i的路径中有一点j使得dis[i] == dis[j] + g[i][j],则val[i] = max(val[i],val[j]+a[i]); 如果dis[i] > dis[j] + g[i][j];则val[i] = val[j] + a[i]; 用最短路算法统计
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cstdlib> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <list> #include <deque> #include <cctype> #include <bitset> #include <cmath> #include <cassert> using namespace std; #define ALL(v) (v).begin(),(v).end() #define cl(a,b) memset(a,b,sizeof(a)) #define bp __builtin_popcount #define pb push_back #define mp make_pair #define fin freopen("D://in.txt","r",stdin) #define fout freopen("D://out.txt","w",stdout) #define lson t<<1,l,mid #define rson t<<1|1,mid+1,r #define seglen (node[t].r-node[t].l+1) #define pi 3.1415926 #define exp 2.718281828459 #define lowbit(x) (x)&(-x) typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef pair<LL,LL> PLL; typedef vector<PII> VPII; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; template <typename T> inline void read(T &x){ T ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; x = ans; } const int maxn = 1000 + 10; int g[maxn][maxn],dis[maxn],a[maxn]; int cnt[maxn],val[maxn],vis[maxn]; void init(int n) { for( int i = 0; i < n; i++ ){ for( int j = 0; j < n; j++ ){ g[i][j] = INF; } dis[i] = INF; } cl(cnt,0); cl(val,0); cl(vis,0); } void dijkstra(int s,int n) { dis[s] = 0; cnt[s] = 1; val[s] = a[s]; for( int i = 1; i < n; i++ ){ int x,mn = INF; for( int j = 0; j < n; j++ ){ if(!vis[j] && dis[j] < mn)mn = dis[x = j]; } vis[x] = 1; for( int j = 0; j < n; j++ ){ if(dis[j] == dis[x] + g[j][x]){ cnt[j] += cnt[x]; val[j] = max(val[j],val[x] + a[j]); } else if(dis[j] > dis[x] + g[j][x]){ cnt[j] = cnt[x]; val[j] = val[x] + a[j]; dis[j] = dis[x] + g[j][x]; } } } } int main() { int n,m,s,e; while(~scanf("%d%d%d%d",&n,&m,&s,&e)){ init(n); for( int i = 0; i < n; i++ ){ scanf("%d",a+i); } for( int i = 0; i < m; i++ ){ int u,v,w; scanf("%d%d%d",&u,&v,&w); g[u][v] = min(g[u][v],w); g[v][u] = g[u][v]; } dijkstra(s,n); printf("%d %d\n",cnt[e],val[e]); } return 0; }