hdu 1142(DFS+dijkstra)

时间:2022-01-15 16:19:30
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<cstdlib>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#include<string.h>
#include<algorithm>
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const int maxNodeNum=1010;//最多节点个数
const int maxEdgeNum=1001000;//最多边条数
const int INF=0x3f3f3f3f;
int n,m;//节点,有向边个数
int mp[maxNodeNum][maxNodeNum];//建立邻接矩阵
int dis[maxNodeNum];//dis[i]为源点到i的最短路径
bool vis[maxNodeNum];//判断某个节点是否已加入集合
int p[maxNodeNum];
void dijkstra(int start)
{
memset(dis,INF,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[start]=0;//一开始集合里没有任何点,下面的循环中,第一个找到的点肯定是源点
for(int i=1;i<=n;i++){
int MinNumber,Min=INF;//MinNumber为dis[]值最小的点的编号
for(int j=1;j<=n;j++)
{
if(dis[j]<Min&&!vis[j])
{
Min=dis[j];
MinNumber=j;
}
}//找到dis[]最小的点,加入集合,更新与其相连的点的dis值
vis[MinNumber]=1;
for(int j=1;j<=n;j++)
if(dis[MinNumber]+mp[MinNumber][j]<dis[j])
dis[j]=dis[MinNumber]+mp[MinNumber][j];
}
}
int DFS(int s)
{
if(p[s]) return p[s];
if(s==2) return 1;
int i,sum=0;
for(i=1;i<=n;i++)
{
if(mp[s][i]<INF&&dis[s]>dis[i])
{
if(p[i]) sum=sum+p[i];
else sum=sum+DFS(i);
}
}
sum=sum+p[s];
p[s]=sum;
return p[s];
}
int main()//109MS
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0)break;
int a,b,c;
memset(mp,INF,sizeof(mp));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c<mp[a][b])
mp[a][b]=mp[b][a]=c;
}
dijkstra(2);
memset(p,0,sizeof(p));
cout<<DFS(1)<<endl;
}
return 0;
}