最短路dijkstra+链式前向星 模板代码
#include <bits/stdc++.h> using namespace std; #define NewNode (ListNode *)malloc(sizeof(ListNode)) #define Mem(a,b) memset(a,b,sizeof(a)) const int N = 1e6 + 5000; const int INF = 0x3f3f3f3f; const double EPS = 1e-10; const unsigned long long mod = 998244353; const int II = 3.1415926535; typedef long long ll; typedef unsigned long long ull; struct node { ll z;//子节点 ll val;//边权值 ll next;//同一父节点的不同子节点存储 }Node[N]; ll head[N],dis[N],num,vis[N];//head是关键,记录父节点的边的编号 void add(ll a,ll b,ll c) { num++; Node[num].z = b; Node[num].val = c; Node[num].next = head[a]; head[a] = num; } int main() { std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); ll n,m,s; cin >> n >> m >> s; for(ll i = 0;i < m;i++) { ll a,b,c; cin >> a >> b >> c; add(a,b,c); } fill(dis,dis+N,INF);//全部赋为无穷大 dis[s] = 0;//s到s的距离为0 ll x = s;//枚举每一个当前最短的s到x的最短路径 while(!vis[x])//跑完全图 { vis[x] = 1;//记忆标记 for(ll i = head[x];i != 0;i = Node[i].next)//把该父节点对应的所有边跑一遍 if(!vis[Node[i].z]) dis[Node[i].z] = min(dis[Node[i].z],dis[x]+Node[i].val); ll Max = INF; for(ll i = 1;i <= n;i++)//枚举当前最短路径 if(!vis[i] && Max > dis[i]) Max = dis[i],x = i; } for(ll i = 1;i <= n;i++) cout << dis[i] << " "; }
上一篇:
IDEA上Java项目控制台中文乱码