淄博seo网站推广,贵州网站建设hsyunso,wordpress 翻页函数,潍坊网站建设wfzhy题目描述
给定一个 n 个点#xff0c;m 条有向边的带非负权图#xff0c;请你计算从 s 出发#xff0c;到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数n,m,s。 第二行起 m 行#xff0c;每行三个非负整数 ui,vi,wi#xff0c;表…题目描述
给定一个 n 个点m 条有向边的带非负权图请你计算从 s 出发到每个点的距离。
数据保证你能从 s 出发到任意点。
输入格式
第一行为三个正整数n,m,s。 第二行起 m 行每行三个非负整数 ui,vi,wi表示从 ui 到 vi 有一条权值为 wi 的有向边。
输出格式
输出一行 n 个空格分隔的非负整数表示 s 到每个点的距离。
输入输出样例
输入
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出
0 2 4 3
这就是一道图。
但是用邻接矩阵太浪费空间了还是用邻接表好一点邻接表用的是动态数组这样会节省空间。
这里定义一个结构体node里面两个int元素to和disto是到达的节点dis表示路径长度让后建立动态数组a数据类型设为node输入时的存储就像这样
a[u].push_back(node{v,w}); 然后就是写搜索函数这道题使用的算法是dijkstra
用在这道题上面那就把点分为两种蓝点和白点蓝点就是没有确定最小值的而白点就是已经确定了的从s开始找他通往的所有蓝点y用数组dis记录到达y点的长度接着再从剩下的蓝点中找一个值最小的标记为白点以他为基础查找与之相连的蓝点如此循环
然后要注意记录dis记录的同时如果元素没被访问就进行入队操作。
最后输出dis数组的值就行了
#includebits/stdc.h
#define int long long
using namespace std;
const int N1e55;
int n,m,s;
struct node{int to,dis;friend bool operator (node a,node b){return a.disb.dis;}
};
priority_queuenodeq;
vectornodea[N];
int dis[N];
int vis[N];
void dij(){for(int i1;in;i)dis[i]INT_MAX;dis[s]0;q.push(node{s,0});while(!q.empty()){node tq.top();q.pop();int xt.to;if(vis[x]1)continue;vis[x]1;for(int i0;ia[x].size();i){int ya[x][i].to;int za[x][i].dis;dis[y]min(dis[y],dis[x]z);if(vis[y]0)q.push(node{y,dis[y]});}}
}
signed main(){scanf(%lld%lld%lld,n,m,s);int u,v,w;for(int i1;im;i){scanf(%lld%lld%lld,u,v,w);a[u].push_back(node{v,w});}dij();for(int i1;in;i)printf(%lld ,dis[i]);
}
