免费网站优化软件,微信支付服务商平台,跨境电商建站公司,只做财经的网站2021.3.10 题目背景 墨家家主发出召集令#xff0c;所有弟子得迅速到指定地点集合。
题目描述 给定一张地图#xff0c;含有n个地点(n10000)#xff0c;地点从1开始编号#xff0c;地图上还含有m条单向路(m100000)连接着这些地点#xff0c;墨家家主在1号位置所有弟子得迅速到指定地点集合。
题目描述 给定一张地图含有n个地点(n10000)地点从1开始编号地图上还含有m条单向路(m100000)连接着这些地点墨家家主在1号位置其余n-1个地点都有一个墨家弟子通过一条路从一个地点到另外一个地点需要花费一定的金钱 第i条路需要花费wiw_iwiwiw_iwi10000)
问所有弟子到墨家家主所在位置至少需要花费多少金钱。
输入格式 第一行两个整数分别是n和m代表n个地点和m条单向路 接下来m行三个整数uvw分别代表这一条路的起点、终点和花费的金钱。
输出格式 一个整数代表至少需要花费的金钱。
输入输出样例 输入 5 10 1 5 3 2 1 2 2 3 7 3 2 7 3 2 8 3 4 10 4 1 10 4 5 9 5 3 10 5 1 1 输出 22 说明/提示 对于25%n10, m100 对于50%n100, m1000 对于75%n1000, m10000 对于100%n10000,m100000,w_i10000。
时限:1.0s 内存:500MB
代码如下
#include iostream
#include cstring
using namespace std;
const int N 10010;
const int MAXCOST 100100;
int vertexnum, arcnum;
int graph[N][N];int dijkstra(int graph[][N], int n, int v) {bool vis[N];int dis[N];memset(vis, 0, sizeof(vis));for (int i 1; i n; i)dis[i] graph[v][i];vis[v] true;for (int i 1; i n - 1; i) {int minx MAXCOST;int minid 0;for (int j 1; j n; j) {if (vis[j] 0 dis[j] minx) {minx dis[j];minid j;}}vis[minid] true;for (int k 1; k n; k) {if (graph[minid][k] MAXCOST)if (dis[k] dis[minid] graph[minid][k]) {dis[k] dis[minid] graph[minid][k];}}}return dis[1];
}int main() {cin vertexnum arcnum;for (int i 1; i vertexnum; i)for (int j 1; j vertexnum; j)if (i j)graph[i][j] 0;elsegraph[i][j] MAXCOST;for (int i 1; i arcnum; i) {int a, b, w;cin a b w;if (graph[a][b] w)graph[a][b] w;}int sum 0;for (int i 2; i vertexnum; i) {int c dijkstra(graph, vertexnum, i);sum c;}cout sum endl;return 0;
}本人水平有限采用了邻接矩阵的Dijkstra算法只能拿50分…还望有大神能给予帮助。
哈哈哈哈哈突然想到了怎么解了发现自己太笨了这题求的是所有其他点(墨家弟子)到起点(墨家家主)的距离之和我居然用dijkstra求每一个点到起点的位置但是其实我们只要将题意转换变成墨家家主到其他所有点的距离之和就变成了用一次dijkstra算法就行了只要输入的时候原本方向是a到b的我们就改成b到a最后用一次dijkstra算法就行了。
AC代码如下
#include iostream
#include cstring
using namespace std;
const int N 10010;
const int MAXCOST 100100;
int vertexnum, arcnum;
int graph[N][N];
bool vis[N];
int dijkstra(int graph[][N], int n, int v) {int dis[N];for (int i 1; i n; i)dis[i] graph[v][i];vis[v] true;for (int i 1; i n - 1; i) {int minx MAXCOST;int minid 0;for (int j 1; j n; j) {if (vis[j] 0 dis[j] minx) {minx dis[j];minid j;}}vis[minid] true;for (int k 1; k n; k) {if (graph[minid][k] MAXCOST)if (dis[k] dis[minid] graph[minid][k]) {dis[k] dis[minid] graph[minid][k];}}}int sum 0;for (int i 1; i n; i) {sum dis[i];}return sum;
}int main() {cin vertexnum arcnum;for (int i 1; i vertexnum; i)for (int j 1; j vertexnum; j)if (i j)graph[i][j] 0;elsegraph[i][j] MAXCOST;for (int i 1; i arcnum; i) {int a, b, w;cin a b w;if (graph[b][a] w)graph[b][a] w;}int sum 0;cout dijkstra(graph, vertexnum, 1);return 0;
}2021.3.25更新 好像才隔了15天。 学会了邻接表实现的dijkstra算法然后再来ac一下这题
代码如下
#include iostream
#include vector
#include queue
#include string
using namespace std;
const int N 10010;
bool done[N];
int dis[N];
const int INF 1 30;
int n, m;struct edge {int from;int to;int w;
};struct node {int id;int dis;friend bool operator(const node a, const node b) {return a.dis b.dis;}
};vectoredgee[N];void dijkstra() {priority_queuenodeq;int s 1;memset(done, 0, sizeof(done));for (int i 1; i n; i)dis[i] INF;dis[s] 0;q.push({s, dis[s]});while (q.size()) {node t q.top();q.pop();if (done[t.id])continue;for (int i 0; i e[t.id].size(); i) {edge y e[t.id][i];if (done[y.to])continue;if (dis[y.to] y.w t.dis) {dis[y.to] y.w t.dis;q.push({y.to, dis[y.to]});}}}int ans 0;for (int i 1; i n; i) {ans dis[i];}cout ans endl;
}int main() {cin n m;while (m--) {int a, b, c;cin a b c;e[b].push_back({b, a, c});}dijkstra();return 0;
}
