Dijkstra求最短路

稠密图 Dijkstra 无负权值

#include
using namespace std;
int n,m;
int dis[1005],vis[1005];		//到达每一点的最小距离 标记
int mp[1005][1005];				//地图 初始化 0x3f3f3f3f
void di(){dis[1]=0;for(int i=1;i<=n;i++){int max=0x3f3f3f3f,index=-1;for(int j=1;j<=n;j++){if(vis[j]&&dis[j]<max){max= dis[j];index=j;}}if(index==-1) return;vis[index]=0;for(int j = 1;j<=n;j++){if(vis[j]&&mp[index][j]!=0x3f3f3f3f){if(dis[index]+mp[index][j]<dis[j]){dis[j] = dis[index]+mp[index][j];}}}}
}
int main(){fill(mp[0],mp[0]+1005*1005,0x3f3f3f3f);fill(dis,dis+1005,0x3f3f3f3f);fill(vis,vis+1005,1);cin>>n>>m;for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;mp[x][y]=min(mp[x][y],z);}di();if(dis[n]!=0x3f3f3f3f)cout<<dis[n];else cout<<-1;
}

稀疏图

#include
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn = 150010;
const int inf  = 0x3f3f3f3f;
priority_queue<PII,vector<PII>,greater<PII>> q ;
int w[maxn],to[maxn],vis[maxn],nex[maxn],now[maxn],dis[maxn];
//  权值	边终点	标记	   同一起点的  目前编号  到达每一点
//							   另一边编号 			 的最小距离 
int indexx,n,m;
void add(int x,int y,int z){to [indexx] = y;w  [indexx] = z;nex[indexx] = now[x];now[x]      = indexx++;
}
int di(){q.push({0,1});			//压入  距离0 端点1 dis[1] = 0;				//起点1 距离0 while(!q.empty()){PII k = q.top();q.pop();int distance = k.first , ver = k.second;if(vis[ver]) continue;vis[ver] = 1;for(int i = now[ver]; i != -1 ; i = nex[i]){ //同起点 不同边 int j = to[i];				if(dis[j] > distance + w[i]){dis[j] = distance + w[i];q.push({dis[j],j});}}}if(dis[n]==inf) cout<<"-1";else cout<<dis[n];
}
int main(){fill(now,now+maxn,-1);fill(dis,dis+maxn,inf);cin>>n>>m;for(int i = 0 ;i < m; i++){int x,y,z;cin>>x>>y>>z;add(x,y,z);}di();
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！