用迪杰斯特拉算法实现有向网的最短路径
输入格式:
第一行输入有向网的顶点和边数,第二行输入各顶点值,用空格间隔,第三行开始输入各条边的 两个点的及边上的权值,用空格间隔。最后一行输入要求路径的两个顶点。
输出格式:
输出最短路径经过的各顶点,中间用-->连接。
输入样例:
在这里给出一组输入。例如:
6 8 0 1 2 3 4 5 0 2 10 0 4 30 0 5 100 1 2 5 2 3 50 3 5 10 4 3 20 4 5 60 0 3
输出样例:
在这里给出相应的输出。例如:
0-->4-->3
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N=1010; struct edge{ int v,w; edge* next; }; struct node{ int k; edge* next; }a[1010]; int n; int find(int u){ for(int i=0;i<n;i++){ if(a[i].k==u){ return i; } } return -1; } void add(int u,int v,int w){ edge* e=new edge(); e->v=v; e->w=w; e->next=a[u].next; a[u].next=e; } int dis[N],pre[N]; bool st[N]; void dijkstra(int u){ memset(pre,-1,sizeof pre); memset(dis,0x3f,sizeof dis); dis[u]=0; for(int i=0;i<n-1;i++){ int k=-1; for(int j=0;j<n;j++){ if(st[j]==0&&(k==-1||dis[j]<dis[k])){ k=j; } } if(dis[k]==0x3f3f3f3f){ continue; } st[k]=1; for(edge* j=a[k].next;j!=NULL;j=j->next){ int v=j->v,w=j->w; if(dis[v]>dis[k]+w){ dis[v]=dis[k]+w; pre[v]=k; } } } } void showRoad(int v){ if(pre[v]!=-1){ showRoad(pre[v]); cout<<"-->"<<a[v].k; }else{ cout<<a[v].k; } } int main(){ int m; cin>>n>>m; for(int i=0;i<n;i++){ int k; cin>>k; a[i].k=k; } for(int i=0;i<m;i++){ int u,v,w; cin>>u>>v>>w; int uu=find(u),vv=find(v); add(uu,vv,w); } int u,v; cin>>u>>v; dijkstra(u); showRoad(v); return 0; }
标签:pre,int,路径,迪杰,最短,斯特拉,next,输入,dis From: https://www.cnblogs.com/kk4458/p/16998300.html