http://acm.hdu.edu.cn/showproblem.php?pid=1142
#include<iostream>
using namespace std;
int n;//十字路口数
int map[1001][1001];
int dist[1001],dp[1001];
void dijkstra(int v)//迪杰斯特拉算法
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int i,j,mins,index;
int *s = new int[n+1];
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
dist[i] = map[i][v];
s[i] = 0;
}
dist[v] = 0;
s[v] = 1;
for(i=1;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mins = 2000000;
for(j=1;j<=n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(s[j]==0 && dist[j]<mins)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mins = dist[j];
index = j;
}
}
if(mins == 2000000)
break;
s[index] = 1;
for(j=1;j<=n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(s[j]==0 && dist[j]>dist[index]+map[j][index])
dist[j] = dist[index]+map[j][index];
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int dfs(int v)//记忆法深搜
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if(dp[v] != -1)
return dp[v];
if(v == 2)
return 1;
int i,temp,sum=0;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(map[v][i]!=2000000 && dist[v] > dist[i])//有路相通而且要去的i点到终点站的距离要比v到终点站的距离小
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
temp = dfs(i);
sum += temp;
}
}
dp[v] = sum;
return sum;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
while(cin>>n && n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int i,j,d,m;
cin>>m;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
dp[i] = -1;
for(j=1;j<=n;j++)
map[i][j] = 2000000;
}
while(m--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d%d%d",&i,&j,&d);
map[i][j] = map[j][i] = d;//无向图
}
//求出各点到终点站的最短距离
dijkstra(2);//2为终点站
dfs(1);//从1出发
cout<<dp[1]<<endl;
}
return 0;
}
|