一开始用的 vector

代码如下：

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int n,m;
bool vis[N];
ll dis[N],dp[N];
vector< pair<int,int> >g[N];
inline void Dijk(){
	for(int i=0;i<=n;i++){
		int u;ll mn=1e18;
		for(int j=0;j<=n;j++)
			if(!vis[j]&&dis[j]<mn)mn=dis[j],u=j;
		if(mn==1e18)break;
		vis[u]=1;
		for(int j=0;j<g[u].size();j++){
			int v=g[u][j].first;
			if(!vis[v])continue;
			int w=g[u][j].second;
			if(dis[u]+dis[v]<dis[w])dp[w]=dp[u]*dp[v];
			else if(dis[u]+dis[v]==dis[w])dp[w]+=dp[u]*dp[v];
			dis[w]=min(dis[w],dis[u]+dis[v]);
		}
	}
}
int main(){
	cin>>n;n--;
	for(int i=0;i<=n;i++)
		scanf("%lld",&dis[i]),dp[i]=1;
	for(int u,v,w;~scanf("%d%d%d",&u,&v,&w);){
		g[u].push_back(make_pair(v,w));
		g[v].push_back(make_pair(u,w));
	}
	Dijk();
	cout<<dis[0]<<' '<<dp[0]<<endl;
	return 0;
}

10pts

然后改邻接矩阵：

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int n,m;
bool vis[N];
ll dis[N],dp[N];
int g[N][N];
inline void Dijk(){
	for(int i=0;i<n;i++){
		int u;ll mn=1e18;
		for(int j=0;j<n;j++)
			if(!vis[j]&&dis[j]<mn)mn=dis[j],u=j;
		if(mn==1e18)break;
		vis[u]=1;
		for(int j=0;j<n;j++){
			int v=j;
			if(!vis[v])continue;
			int w=g[u][v];
            if(w==-1)continue;
			if(dis[u]+dis[v]<dis[w])dp[w]=dp[u]*dp[v];
			else if(dis[u]+dis[v]==dis[w])dp[w]+=dp[u]*dp[v];
			dis[w]=min(dis[w],dis[u]+dis[v]);
		}
	}
}
int main(){
	cin>>n;
    memset(g,-1,sizeof g);
	for(int i=0;i<n;i++)
		scanf("%lld",&dis[i]),dp[i]=1;
	for(int u,v,w;~scanf("%d%d%d",&u,&v,&w);){
		g[u][v]=g[v][u]=w;
	}
	Dijk();
	cout<<dis[0]<<' '<<dp[0]<<endl;
	return 0;
}

于是过了，怀疑是数据问题