Dijkstra算法

#include<bits/stdc++.h> using namespace std; struct Edge{ int next; int cost; }; vector<Edge> v[101]; int Dis[101]; bool mark[101]; int main(){ long long num; long long val,temp1,temp2,temp3; while(scanf("%lld",&num)!=EOF&&num!=0){ scanf("%lld",&val); for(int i=0;i<=num;i++) Dis[i]=INT_MAX; memset(mark,0,sizeof(mark)); for(int i=1;i<=num;i++) v[i].clear(); for(int i=0;i<val;i++){ scanf("%lld%lld%lld",&temp1,&temp2,&temp3); Edge tmp; tmp.next=temp2; tmp.cost=temp3; v[temp1].push_back(tmp); tmp.next=temp1; v[temp2].push_back(tmp); } Dis[1]=0; mark[1]=true; int newP=1; //重复n-1次,因为有n-1个结点距离未知。 for(int k=1;k<num;k++){ int size=v[newP].size(); //更新距离 for(int i=0;i<size;i++){ int t_cost=v[newP][i].cost; int t_next=v[newP][i].next; //这里不可达与更短距都要更新 if(!mark[t_next]&&(Dis[newP]==INT_MAX||Dis[newP]+t_cost<Dis[t_next])) Dis[t_next]=t_cost+Dis[newP]; } //选择最小距离 int min=INT_MAX; for(int j=1;j<=num;j++){ if(!mark[j]&&Dis[j]<min){ min=Dis[j]; newP=j; } } mark[newP]=true; } cout<<Dis[num]<<endl; } return 0; }

1447