Description
小明来到青岛上学已经一年了，他给青岛这座城市画了一张地图。在这个地图上有n个点，小明的起始点为1号点，终点为n号点，并且地图上的所有边都是单向的。小明知道从i号点到j号点的时间花费为w分钟，那么问题来了，求从1号点到n号的最小时间花费是多少？这个最少花费的路径有多少条？
Input
输入格式：输入文件第一行为两个空格隔开的数n，m，表示这张地图里有多少个点及有多少边的信息。下面m行，每行三个数I、J、w，表示从I点到J点有道路相连且花费为w.（注意，数据提供的边信息可能会重复，不过保证I<>J,1<=I,J<=n）。1<=N<=2100,0<=m<=N*(N-1), 1<=w<=2100.
Output
输出格式：输出文件包含两个数，分别是最少花费和花费最少的路径的总数.两个不同的最短路方案要求：路径长度相同（均为最短路长度）且至少有一条边不重合。若城市N无法到达则只输出一个(‘No answer’);
Sample Input 1
5 4 1 5 4 1 2 2 2 5 2 4 1 1
Sample Output 1
4 2
Sample Input 2
100 1 1 2 1
Sample Output 2
No answer
最短路+暴力找路径条数
代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<set> #include<vector> #include<cmath>const int maxn=1e5+5; typedef long long ll; const ll Inf=0x3f3f3f3f3f3f3f; using namespace std;struct node {int to;ll w; }; ll map[2105][2105]; vector<node>vec[2105]; int vis1[2105][2105]; int vis[2105]; ll dis[2105]; int n,m; void Init () {for(int t=1;t<=n;t++){for(int j=1;j<=n;j++){map[t][j]=Inf;}}for(int i=1;i<=n;i++){map[i][i]=0;} } void Getmap() {int u,v;ll w;for(int t=1;t<=m;t++){scanf("%d%d%lld",&u,&v,&w);if(map[u][v]>w)map[u][v]=w;if(vis1[u][v]!=w){node s;s.to=v;s.w=w;vec[u].push_back(s);}vis1[u][v]=w;} } void Dijkstra(int u) {memset(vis,0,sizeof(vis));for(int t=1;t<=n;t++){dis[t]=map[u][t];}vis[u]=1;for(int t=1;t<n;t++){ll minn=Inf,temp;for(int i=1;i<=n;i++){if(!vis[i]&&dis[i]<minn){minn=dis[i];temp=i;}}vis[temp]=1;for(int i=1;i<=n;i++){if(map[temp][i]+dis[temp]<dis[i]){dis[i]=map[temp][i]+dis[temp];}}} } ll bfs() {ll sss=0;queue<node>q;for(int t=0;t<vec[1].size();t++){node nn=vec[1][t];if(nn.w<=dis[n]) q.push(vec[1][t]); }while(!q.empty()){node now=q.front();q.pop();if(now.to==n){if(now.w==dis[n]){sss++;}}for(int t=0;t<vec[now.to].size();t++){node after=vec[now.to][t];after.to=after.to;after.w=now.w+after.w;if(after.w<=dis[n])q.push(after); }}return sss; } int main() {scanf("%d%d",&n,&m);Init();Getmap();Dijkstra(1);if(dis[n]!=Inf){ll ans=bfs();printf("%lld %lld\n",dis[n],ans);}else{printf("No answer\n");}return 0; }
