B1003 Emergency (25分)
//题中要注意输出的是最短路条数,而不是最短路长度
- 更新路径长度时带上点权
if (路径可以更短)
{
更新路径长度
加上点权
更新最短路条数//num[u]=num[v];
}
else if(路径长度相等)
{
if(可以得到更大的点权)
更新点权
更新最短路条数//num[u]+=num[v];
}
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=550;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=633;
int book[MAX];
int G[MAX][MAX];
int dis[MAX],res[MAX];
int c[MAX],num[MAX];
int n,m,st,se;
void dijkstra(int start)
{
fill(dis,dis+MAX,INF);
memset(res,0,sizeof(res));
memset(num,0,sizeof(num));
dis[start]=0;
num[start]=1;
res[start]=c[start];
for(int i=0;i<n;i++)
{
int MIN=INF,u=-1;
for(int j=0;j<n;j++)
{
if(book[j]==0&&dis[j]<MIN)
{
u=j;
MIN=dis[j];
}
}
if(u==-1)
return ;
book[u]=1;
for(int v=0;v<n;v++)
{
if(book[v]==0&&G[u][v]!=INF)
{
if(dis[u]+G[u][v]<dis[v])
{
dis[v]=dis[u]+G[u][v];
res[v]=res[u]+c[v];
num[v]=num[u];
}
else if(dis[u]+G[u][v]==dis[v])
{
if(res[u]+c[v]>res[v])
res[v]=res[u]+c[v];
num[v]+=num[u];
}
}
}
}
}
int main()
{
memset(book,0,sizeof(book));
fill(G[0],G[0]+MAX*MAX,INF);
scanf("%d%d%d%d",&n,&m,&st,&se);
for(int i=0;i<n;i++)
scanf("%d",&c[i]);
for(int i=0;i<m;i++)
{
int x,y,d;
scanf("%d%d%d",&x,&y,&d);
G[x][y]=d;
G[y][x]=d;
}
dijkstra(st);
printf("%d %d\n",num[se],res[se]);
return 0;
}