求出有n(1 < n <= 100)个结点有向图中，结点1到结点n的最短路径，以及最短路径的条数。
Input
第一行有2个整数n和m( 0 < m < 3000)，接下来m行每行有三个整数u,v,w结点u到v之间有一条权为w的边(w<100000)。
Output
输出只有一行，为结点1到结点n之间的最短路径及其条数(用空格隔开)，如果1到n之间不存在路径，输出 -1 0。
Sample Input
3 3
1 2 10
2 3 15
1 3 25
Sample Output
25 2
分析：本题中两相邻点间可能存在多条路，但每条路长度相同，这点在题中并没有说明。
思路：做两次dijkstra即可，第一次用于求出各点到源点的最短距离。第二次用于统计最短路条数。分两类统计：一类为最短路间没有中间定点的，另一类为最短路间有中间顶点的。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <algorithm>using namespace std;
int cost[101][101],path[101][101],low[101],dis[101],num[101]={};//low和dis数组分别是两次dijkstra的当前i点到源点的最短路
bool vis[101]; //path保存两点间路径条数
const int MAXN=10000001; //num保存点到源点最短路径数目int main()
{int n,m,i,j,k;memset(vis,false,sizeof(vis));scanf("%d%d",&n,&m);for(i=0;i<101;++i){ //初始化代价矩阵for(j=0;j<101;++j){cost[i][j]=MAXN;}}for(i=0;i<m;++i){ //读数据int a,b,c;scanf("%d%d%d",&a,&b,&c);cost[a][b]=c;path[a][b]++;}vis[1]=true; //第一次dijkstra求最短路for(i=2;i<=n;++i)low[i]=cost[1][i];for(i=2;i<=n;++i){int minn=MAXN+1;for(j=1;j<n;++j){if(!vis[j] && low[j]<minn){minn=low[j];k=j;}}vis[k]=true;for(j=1;j<=n;++j){if(!vis[j]){low[j]=min(low[j],low[k]+cost[k][j]);}}}memset(vis,false,sizeof(vis));vis[1]=true; //第二次dijkstra求最短路条数，最短路分两类，一类直达，一类借助中间点达for(i=2;i<=n;++i) dis[i]=cost[1][i];for(i=2;i<=n;++i) //第一类直达if(dis[i]==low[i])num[i]=path[1][i];for(i=2;i<=n;++i){int minn=MAXN+1;for(j=1;j<=n;++j){if(!vis[j] && dis[j]<minn){minn=dis[j];k=j;}}vis[k]=true;for(j=1;j<=n;++j){if(!vis[j]){dis[j]=min(dis[j],dis[k]+cost[k][j]);}if(dis[k]+cost[k][j]==low[j]) //统计第二类，通过中间点到达的路径数目num[j]+=num[k]*path[k][j];}}if(low[n]>=MAXN)printf("-1 0\n");elseprintf("%d %d\n",low[n],num[n]);return 0;
}
