pat1003
// 1003.cpp : 定义控制台应用程序的入口点。 //
#include "stdafx.h" #include <iostream> #include <algorithm> using namespace std; int n, m, c1, c2;//n is amount of vertex,m is amount of edge,c1 is start vertex,c2 is end vertex int e[510][510];//using a adjacency matrix to store the graph int weight[510]; int dis[510], num[510], w[510]; bool visit[510]; const int inf = 99999999; int main() { cin >> n >> m >> c1 >> c2; for (int i = 0; i < n; i++) cin >> weight[i]; fill(e[0], e[0] + 510 * 510, inf); fill(dis, dis + 510, inf); int a, b, c; for (int i = 0; i < m; i++) { cin >> a >> b >> c; e[a][b] = e[b][a] = c; } dis[c1] = 0;//mark the start vertex w[c1] = weight[c1]; num[c1] = 1; for (int i = 0; i < n; i++) { int u = -1, minn = inf; for (int j = 0; j < n; j++) { if (visit[j] == false && dis[j] < minn) { u = j; minn = dis[j]; } } if (u == -1) break; visit[u] = true; for (int v = 0; v < n; v++) { if (visit[v] == false && e[u][v] != inf) {// && make sure the vertex have edge connect with current vertex if (dis[u] + e[u][v] < dis[v]) { dis[v] = dis[u] + e[u][v]; num[v] = num[u]; w[v] = w[u] + weight[v]; } else if (dis[u] + e[u][v] == dis[v]) { num[v] = num[v] + num[u]; if (w[u] + weight[v] > w[v]) w[v] = w[u] + weight[v]; } } } } printf("%d %d", num[c2], w[c2]); return 0; }
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄
#include "stdafx.h" #include <iostream> #include <algorithm> using namespace std; int n, m, c1, c2;//n is amount of vertex,m is amount of edge,c1 is start vertex,c2 is end vertex int e[510][510];//using a adjacency matrix to store the graph int weight[510]; int dis[510], num[510], w[510]; bool visit[510]; const int inf = 99999999; int main() { cin >> n >> m >> c1 >> c2; for (int i = 0; i < n; i++) cin >> weight[i]; fill(e[0], e[0] + 510 * 510, inf); fill(dis, dis + 510, inf); int a, b, c; for (int i = 0; i < m; i++) { cin >> a >> b >> c; e[a][b] = e[b][a] = c; } dis[c1] = 0;//mark the start vertex w[c1] = weight[c1]; num[c1] = 1; for (int i = 0; i < n; i++) { int u = -1, minn = inf; for (int j = 0; j < n; j++) { if (visit[j] == false && dis[j] < minn) { u = j; minn = dis[j]; } } if (u == -1) break; visit[u] = true; for (int v = 0; v < n; v++) { if (visit[v] == false && e[u][v] != inf) {// && make sure the vertex have edge connect with current vertex if (dis[u] + e[u][v] < dis[v]) { dis[v] = dis[u] + e[u][v]; num[v] = num[u]; w[v] = w[u] + weight[v]; } else if (dis[u] + e[u][v] == dis[v]) { num[v] = num[v] + num[u]; if (w[u] + weight[v] > w[v]) w[v] = w[u] + weight[v]; } } } } printf("%d %d", num[c2], w[c2]); return 0; }
更多精彩
