A traveler's map gives the distances between cities along the highways, together with the cost of each highway.
Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination.
If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.
DECLARE: The test data in PAT is wrong,we strengthened the test data.If the same code got passed in pat,it may not be able to get passed in NOWCODER,please check your code.(This means that our test data is no problem,I guarantee.)
[编程题]Travel Plan (30)
- 热度指数：2712 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (<=500) is the number of cities (and hence the cities are numbered from 0 to N-1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:
City1 City2 Distance Cost
where the numbers are all integers no more than 500, and are separated by a space.
输出描述:
For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.
示例1
输入
4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20
输出
0 2 3 3 40
我也是日了狗了，PAT网站上能过，这里就死活不能过，你们能统一一点吗
import java.util.Scanner; import java.util.Stack; public class Main { public int[][] graph; public int[][] cost; public int V,E,st,end; public int[] distTo; public int[] edgeTo; public boolean[] visited; public int[] costTo; public void run() { init(); Dijkstra(); print(); } public void print() { Stack<Integer> stack = new Stack<Integer>(); int i = end; while(edgeTo[i] != -1) { stack.push(i); i = edgeTo[i]; } stack.push(st); while(!stack.isEmpty()) { System.out.print(stack.pop()+" "); } System.out.print(distTo[end]+" "+costTo[end]); } public void Dijkstra() { for(int i = 0; i < V; i++) { int min = (int) Double.POSITIVE_INFINITY; int index = 0; for(int j = 0; j < V; j++) { if(!visited[j]) { if(min > distTo[j]) { min = distTo[j]; index = j; } } } visited[index] = true; for(int j = 0; j < V; j++) { if(!visited[j] && graph[index][j]!=-1) { if(distTo[j] > graph[index][j] + distTo[index]) { distTo[j] = graph[index][j] + distTo[index]; edgeTo[j] = index; costTo[j] = cost[index][j] + costTo[index]; } else if(distTo[j] == graph[index][j] + distTo[index]) { if(costTo[j] > cost[index][j] + costTo[index]) { distTo[j] = graph[index][j] + distTo[index]; edgeTo[j] = index; costTo[j] = cost[index][j] + costTo[index]; } } } } } } public void init() { Scanner in = new Scanner(System.in); V = in.nextInt(); E = in.nextInt(); st = in.nextInt(); end = in.nextInt(); graph = new int[V][V]; cost = new int[V][V]; distTo = new int[V]; edgeTo = new int[V]; visited = new boolean[V]; costTo = new int[V]; for(int i =0; i < V; i++) for(int j=0; j < V; j++) { graph[i][j] = cost[i][j] = -1; } for(int j = 0; j < E; j++) { int from,to,dis,co; from = in.nextInt(); to = in.nextInt(); dis = in.nextInt(); co = in.nextInt(); if(graph[from][to] == -1 ||(graph[from][to]!=-1 && cost[from][to] > co)) { graph[from][to] = graph[to][from] = dis; cost[from][to] = cost[to][from] = co; } } in.close(); for(int i = 0; i < V; i++) { distTo[i] = costTo[i] = (int) Double.POSITIVE_INFINITY; edgeTo[i] = -1; } distTo[st] = 0; costTo[st] = 0; edgeTo[st] = -1; } public static void main(String[] args) { // TODO Auto-generated method stub Main pat = new Main(); pat.run(); } }
发表于 2016-04-14 14:14:10
回复(3)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=510;
const int INF=10000000;
bool vis[maxn]={false};
int n,m,start,final,G[maxn][maxn],d[maxn];
int cost[maxn][maxn],c[maxn],pre[maxn]; //cost为对应的边的花费，c记录最小花费
void Dijkstra(int s){
fill(d,d+maxn,INF);d[s]=0; //初始化d，c，pre
fill(c,c+maxn,INF);c[s]=0;
for(int i=0;i<n;i++) pre[i]=i;
for(int i=0;i<n;i++){
int u=-1,min=INF;
for(int j=0;j<n;j++){
if(vis[j]==false&&d[j]<min){
u=j;min=d[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
c[v]=c[u]+cost[u][v];
pre[v]=u;
}
else if(d[u]+G[u][v]==d[v]&&c[u]+cost[u][v]<c[v]){
c[v]=c[u]+cost[u][v];
pre[v]=u;
}
}
}
}
}
void print(int v){ //打印路径
if(v==start){
cout<<v<<" ";
return;
}
print(pre[v]);
cout<<v<<" ";
}
int main(){
cin>>n>>m>>start>>final;
int u,v;
fill(G[0],G[0]+maxn*maxn,INF);
for(int i=0;i<m;i++){
cin>>u>>v;
cin>>G[u][v]>>cost[u][v];
G[v][u]=G[u][v];
cost[v][u]=cost[u][v];
}
Dijkstra(start);
print(final); //打印路径
cout<<d[final]<<" "<<c[final];
return 0;
}
发表于 2019-02-09 16:18:57
回复(0)
package go.jacob.day1123;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* 1030. Travel Plan (30)
* @author Jacob
*
*/
public class Demo1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), M = sc.nextInt(), S = sc.nextInt(), D = sc.nextInt();
// 生成图
Graph graph = new Graph(N, M);
for (int i = 0; i < M; i++) {
Edge e = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
graph.addEdge(e);
}
Dijkstra d = new Dijkstra(graph, S, D);
d.getPath();
ArrayList<Integer> res = getRes(d, D);
for (int i = res.size() - 1; i >= 0; i--) {
System.out.print(res.get(i) + " ");
}
System.out.println(d.distTo[D] + " " + d.costTo[D]);
sc.close();
}
private static ArrayList<Integer> getRes(Dijkstra d, int des) {
ArrayList<Integer> list = new ArrayList<Integer>();
int tmp = des;
while (tmp != -1) {
list.add(tmp);
tmp = d.pathTo[tmp];
}
return list;
}
}
/*
* 迪杰斯特拉算法类
*/
class Dijkstra {
Graph g;
public Integer[] distTo;// 节点到起点的距离
public Integer[] costTo;// 节点到起点的开销
public Integer[] pathTo;
private boolean[] visited;// 节点是否被访问
private int src;
private int des;
public Dijkstra(Graph g, int src, int des) {
this.g = g;
this.src = src;
this.des = des;
distTo = new Integer[g.getCityNum()];
costTo = new Integer[g.getCityNum()];
pathTo = new Integer[g.getCityNum()];
visited = new boolean[g.getCityNum()];
for (int i = 0; i < g.getCityNum(); i++) {
distTo[i] = Integer.MAX_VALUE;
costTo[i] = Integer.MAX_VALUE;
visited[i] = false;
}
}
public void getPath() {
distTo[src] = 0;
costTo[src] = 0;
pathTo[src] = -1;
int city = src;
while (true) {
if (city == -1)
break;
visited[city] = true;
relax(city);
int min = Integer.MAX_VALUE, index = -1;
for (int i = 0; i < g.getCityNum(); i++) {
if (!visited[i] && distTo[i] < min) {
min = distTo[i];
index = i;
}
}
city = index;
}
}
public void relax(int v) {
List<Edge> adj = g.adj(v);
for (Edge e : adj) {
if (distTo[e.either(v)] > distTo[v] + e.getDist()) {
distTo[e.either(v)] = distTo[v] + e.getDist();
pathTo[e.either(v)] = v;
costTo[e.either(v)] = costTo[v] + e.getCost();
} else if (distTo[e.either(v)] == distTo[v] + e.getDist()) {
if (costTo[e.either(v)] > costTo[v] + e.getCost()) {
pathTo[e.either(v)] = v;
costTo[e.either(v)] = costTo[v] + e.getCost();
}
}
}
}
}
/*
* 图类
*/
class Graph {
private int cityNum, highwayNum;
private ArrayList<Edge>[] bag;
@SuppressWarnings("unchecked")
public Graph(int cityNum, int highwayNum) {
this.cityNum = cityNum;
this.highwayNum = highwayNum;
bag = new ArrayList[cityNum];
for (int i = 0; i < cityNum; i++) {
bag[i] = new ArrayList<Edge>();
}
}
public List<Edge> adj(int v) {
return bag[v];
}
public void addEdge(Edge e) {
bag[e.getV()].add(e);
bag[e.getW()].add(e);
}
public int getCityNum() {
return cityNum;
}
public int getHighwayNum() {
return highwayNum;
}
public ArrayList<Edge>[] getBag() {
return bag;
}
}
/*
* 加权边类
*/
class Edge {
private int v;
private int w;
private int dist;
private int cost;
public Edge(int v, int w, int dist, int cost) {
super();
this.v = v;
this.w = w;
this.dist = dist;
this.cost = cost;
}
public int either(int i) {
return i == v ? w : v;
}
public int getV() {
return v;
}
public int getW() {
return w;
}
public int getDist() {
return dist;
}
public int getCost() {
return cost;
}
}
编辑于 2017-11-28 09:19:22
回复(0)
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500 + 10;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
struct Dijkstra{
struct Edge{
int to;
int dist, cost;
Edge() {}
void set_value(int v, int d, int c){
to = v;
dist = d;
cost = c;
}
};
vector<Edge> G[maxn];
// vector<Edge> edges;
int d[maxn], done[maxn], pay[maxn];
int pre[maxn];
int n, m;
void init(int param1, int param2){
n = param1;
m = param2;
for(int i=0; i<m; i++){
int city1, city2, dist, cost;
scanf("%d %d %d %d", &city1, &city2, &dist, &cost);
Edge e;
e.set_value(city2, dist, cost);
G[city1].push_back(e);
e.to = city1;
G[city2].push_back(e);
}
}
void dijkstra(int s){
priority_queue<pii, vector<pii>, greater<pii> > Q;
memset(done, 0, sizeof(done));
memset(pay, INF, sizeof(pay));
memset(d, INF, sizeof(d));
memset(pre, -1, sizeof(pre));
d[s] = 0;
pay[s] = 0;
Q.push(make_pair(d[s], s));
while(!Q.empty()){
pii p = Q.top();
Q.pop();
int u = p.second;
if(done[u]) continue;
done[u] = true;
for(unsigned int i=0; i<G[u].size(); i++){
Edge e = G[u][i];
int v = e.to;
if(done[v]) continue;
if(d[v] > d[u] + e.dist || (d[v] == d[u] + e.dist && pay[v] > pay[u] + e.cost)){
pay[v] = pay[u] + e.cost;
d[v] = d[u] + e.dist;
pre[v] = u;
Q.push(make_pair(d[v], v));
}
}
}
}
void show_road(int s){
if(s == -1) return;
else{
show_road(pre[s]);
printf("%d ", s);
}
}
void show_dist_cost(int s){
printf("%d %d\n", d[s], pay[s]);
}
};
int main(){
int N, M, S, D;
scanf("%d %d %d %d", &N, &M, &S, &D);
Dijkstra g;
g.init(N, M);
g.dijkstra(S);
g.show_road(D);
g.show_dist_cost(D);
return 0;
}
编辑于 2017-09-08 18:55:38
回复(0)
我觉得我写的很详细
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int const MaxVertexNum = 500;
#define INFINITY 65535
#define Vertex int
#define WeightType int
//***********边的定义*************//
struct Enode{
Vertex V1,V2;
WeightType Weight;
WeightType Money;
};
typedef Enode *Edge;
//*************图节点定义************//
struct Gnode{
int Nv;//顶点数
int Ne;//边数
WeightType G[MaxVertexNum][MaxVertexNum];
WeightType M[MaxVertexNum][MaxVertexNum];
};
typedef Gnode *MGraph;
//***************函数声明*****************//
MGraph CreateGraph(int VertexNum);
void InsertEdge(MGraph Graph, Edge E);
MGraph BuildGraph(Vertex &S, Vertex &D);
Vertex FindMinDist(MGraph Graph, int dist[],int collected[]);
bool Dijkstra(MGraph Graph, int dist[],int path[],int cost[],Vertex S);
void FindThePathOut(MGraph Graph,Vertex S,Vertex D);
int main(){
MGraph Graph;
Vertex S,D;
Graph = BuildGraph(S, D);
FindThePathOut(Graph, S, D);
return 0;
}
//*****************以下是建立图数据结构*****************//
MGraph CreateGraph(int VertexNum){
MGraph Graph;
Graph = new Gnode;
Graph->Nv = VertexNum;
Graph->Ne = 0;
for (Vertex V=0; V < Graph->Nv; ++V) {
for (Vertex W=0; W < Graph->Nv; ++W) {
Graph->G[V][W] = INFINITY;
Graph->M[V][W] = INFINITY;
}
}
return Graph;
}
void InsertEdge(MGraph Graph, Edge E){
Graph->G[E->V1][E->V2] = E->Weight;
Graph->M[E->V1][E->V2] = E->Money;
Graph->G[E->V2][E->V1] = E->Weight;
Graph->M[E->V2][E->V1] = E->Money;
}
MGraph BuildGraph(Vertex &S,Vertex &D){
MGraph Graph;
Edge E;
Vertex Nv;
cin >> Nv;
Graph = CreateGraph(Nv);
cin >> Graph->Ne >> S >> D;
if (Graph->Ne != 0) {
E = new Enode;
for (int i=0; i < Graph->Ne; ++i) {
cin >> E->V1 >> E->V2 >> E->Weight >> E->Money;
InsertEdge(Graph, E);
}
}
return Graph;
}
//*********************建立图结束*******************//
//*********************以下是最短路径算法**********************//
bool Dijkstra(MGraph Graph, int dist[],int path[],int cost[],Vertex S){
int collected[Graph->Nv];
Vertex V;
for (V=0; V < Graph->Nv; ++V) {
dist[V] = Graph->G[S][V];
cost[V] = Graph->M[S][V];
path[V] = S;
collected[V] = false;
}
dist[S] = 0;cost[S] = 0;collected[S] = true;
while (true) {
V = FindMinDist(Graph, dist, collected);
if (V == -1) {
break;
}
collected[V] = true;
for (Vertex W=0; W < Graph->Nv; ++W) {
if (collected[W]==false && Graph->G[V][W] < INFINITY) {
if (Graph->G[V][W] < 0) {
return false;
}
if (dist[V] + Graph->G[V][W] < dist[W]) {
dist[W] = dist[V] + Graph->G[V][W];
path[W] = V;
cost[W] = cost[V] + Graph->M[V][W];
}
else if (dist[V]+Graph->G[V][W]==dist[W] && cost[V]+Graph->M[V][W]<cost[W]){
dist[W] = dist[V] + Graph->G[V][W];
path[W] = V;
cost[W] = cost[V] + Graph->M[V][W];
}
}
}
}
return true;
}
Vertex FindMinDist(MGraph Graph,int dist[],int collected[]){
Vertex MinV=0;
int MinDist = INFINITY;
for (Vertex V=0; V < Graph->Nv; ++V) {
if (collected[V] == false && dist[V] < MinDist) {
MinDist = dist[V];
MinV = V;
}
}
if (MinDist < INFINITY) {
return MinV;
}
else{
return -1;
}
}
//********************最短路劲算法结束**********************//
void FindThePathOut(MGraph Graph,Vertex S,Vertex D){
int dist[Graph->Nv];
int path[Graph->Nv];
int cost[Graph->Nv];
Dijkstra(Graph, dist, path, cost, S);
vector<Vertex> ThePath;
Vertex P = D;
ThePath.push_back(P);
while (P != S) {
ThePath.push_back(path[P]);
P = path[P];
}
for (auto it = ThePath.rbegin(); it != ThePath.rend(); ++it) {
cout << *it << ' ';
}
cout << dist[D] << ' ' << cost[D] << endl;
}
发表于 2016-08-22 15:21:05
回复(1)
使用深度遍历找出最短的路径，若路径相同，则选择cost较小的
#include <iostream>
#include <vector>
#include <memory.h>
using namespace std;
const int maxn = 501;
const int maxdis = 99999;
const int maxcost = 99999;
class Path {
public:
vector<int> path;
int dist;
int cost;
};
int n, m, s, d;
int dis[maxn][maxn];
int cost[maxn][maxn];
bool visit[maxn] = { false };
Path minPath;
int mindist = maxdis;
int mincost;
void DFS(int u, int v, Path path) {
// u为起点，v是终点
if (u == v) {
if (path.dist < minPath.dist) {
minPath = path;
}
else if (path.dist == minPath.dist) {
if (path.cost < minPath.cost) {
minPath = path;
}
}
return;
}
for (int i = 0; i < n; i++) {
if (!visit[i] && dis[u][i] != maxdis) {
if (path.dist + dis[u][i] <= minPath.dist) {
visit[i] = true;
path.path.push_back(i);
path.dist += dis[u][i];
path.cost += cost[u][i];
DFS(i, v, path);
visit[i] = false;
path.path.pop_back();
path.dist -= dis[u][i];
path.cost -= cost[u][i];
}
}
}
}
int main() {
cin >> n >> m >> s >> d;
// 初始化minPath，dis和cost
minPath.cost = maxcost;
minPath.dist = maxdis;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dis[i][j] = maxdis;
cost[i][j] = maxcost;
}
}
for (int i = 0; i < m; i++) {
int c1, c2, d, c;
cin >> c1 >> c2 >> d >> c;
dis[c1][c2] = d;
dis[c2][c1] = d;
cost[c1][c2] = c;
cost[c2][c1] = c;
}
Path path;
path.dist = 0;
path.cost = 0;
path.path.push_back(s);
visit[s] = true;
DFS(s, d, path);
for (size_t i = 0; i < minPath.path.size(); i++) {
cout << minPath.path[i] << " ";
}
cout << minPath.dist << " " << minPath.cost;
return 0;
}
发表于 2020-09-21 20:04:18
回复(0)
本地可以跑，但是服务器结果不一致，为什么？
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
struct E
{
int nextId;
int dis;
int cost;
};
vector<int> maxpath;
int maxcost = 123123123;
vector<int> path;
bool visited[101];
void dfs(vector<E> nodes[101],int index,int N,int desid,int cost,int shortdis,int dis)
{
if(index==desid)
{
if(dis==shortdis)
{
//输出
if(maxcost>cost)
{
maxcost = cost;
maxpath.clear();
for(int i=0;i<path.size();i++)
{
maxpath.push_back(path[i]);
}
}
}
return;
}
path.push_back(index);
visited[index] = true;
for(int i=0;i<nodes[index].size();i++)
{
int nextId = nodes[index][i].nextId;
int nextCost = cost+nodes[index][i].cost;
int nextDis = dis+nodes[index][i].dis;
if(visited[nextId])
{
continue;
}
dfs(nodes,nextId,N,desid,nextCost,shortdis,nextDis);
}
visited[index] = false;
path.pop_back();
}
int main()
{
for(int i=0;i<101;i++)
{
visited[i]=false;
}
vector<E> nodes[101];
bool mark[101];
int shortestdis[101];
int N,M,S,D;
scanf("%d %d %d %d",&N,&M,&S,&D);
for(int i=0;i<N;i++)
{
nodes[N].clear();
mark[i]=false;
shortestdis[i] = -1;//很大的数字
}
for(int i=0;i<M;i++)
{
int a,b,dis,cost;
scanf("%d %d %d %d",&a,&b,&dis,&cost);
E tmp;
tmp.cost = cost;
tmp.dis = dis;
tmp.nextId = b;
nodes[a].push_back(tmp);
E tmp2;
tmp2.cost = cost;
tmp2.dis = dis;
tmp2.nextId = a;
nodes[b].push_back(tmp2);
}
//找最短路径dijkstra算法
mark[0] = true;
shortestdis[0]=0;
int current = 0;
for(int i=1;i<N;i++)
{
for(int j=0;j<nodes[current].size();j++)
{
int next = nodes[current][j].nextId;
int dis = nodes[current][j].dis;
int cost = nodes[current][j].cost;
if(mark[next]==true) continue;
if(shortestdis[next]==-1||shortestdis[current]+dis<shortestdis[next])
{
shortestdis[next] = shortestdis[current]+dis;
}
}
int min = 123123123;
for(int j=1;j<=N;j++)
{
if(mark[j]) continue;
if(shortestdis[j]==-1) continue;
if(shortestdis[j]<min)
{
current = j;
min = shortestdis[j];
}
}
mark[current] = true;
}
dfs(nodes,S, N,D,0,shortestdis[D],0);
for(int i=0;i<maxpath.size();i++)
{
cout<<maxpath[i]<<" ";
}
cout<<D<<" "<<shortestdis[D]<<" "<<maxcost<<endl;
return 0;
}
发表于 2018-03-02 16:54:47
回复(0)
总有测试用例过不去，求帮忙看看哪里错了。
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Solution solution = new TravelPlan();
solution.input();
solution.deal();
solution.output();
}
}
class TravelPlan extends MiddleSolution {
String startCity;
String endCity;
int cityCount;
Graph g = new Graph();
@Override
public void input() {
cityCount = scanner.nextInt();
int lineCount = scanner.nextInt();
startCity = scanner.next();
endCity = scanner.next();
while (lineCount > 0) {
String fromCity = scanner.next();
String toCity = scanner.next();
int length = scanner.nextInt();
int money = scanner.nextInt();
if (Integer.valueOf(fromCity) >= cityCount
|| Integer.valueOf(endCity) >= cityCount) {
lineCount--;
continue;
}
g.addEdge(fromCity, toCity, new Graph.Cost(length, money));
lineCount--;
}
}
@Override
public void deal() throws Exception {
g.dijkstra(startCity, endCity);
}
@Override
public void output() {
System.out.print(printListWithSpace(g.getPath(startCity, endCity)));
Graph.Cost cost = g.getCost(endCity);
System.out.print(" " + cost.length + " " + cost.money);
}
}
class Graph {
public static final Cost INFINITY = new Cost(Integer.MAX_VALUE ,
Integer.MAX_VALUE );
public static final Cost NO_COST = new Cost(0, 0);
private Map<String, Vertex> vertexMap = new HashMap<String, Vertex>();
public void addEdge(String sourceName, String destName, Cost cost) {
Vertex from = getVertex(sourceName);
Vertex dest = getVertex(destName);
from.adj.add(new Edge(dest, cost));
}
public void dijkstra(String startName, String destName) throws Exception {
PriorityQueue<Path> pq = new PriorityQueue<Path>();
Vertex start = vertexMap.get(startName);
Vertex end = vertexMap.get(destName);
if (start == null || end == null) {
throw new Exception();
}
clearAll();
pq.add(new Path(start, NO_COST));
start.cost = NO_COST;
while (!pq.isEmpty()) {
Path path = pq.remove();
Vertex vertex = path.dest;
if (vertex.scratch != 0) {
continue;
}
vertex.scratch = 1;
if (vertex == end) {
return;
}
for (Edge edge : vertex.adj) {
Vertex next = edge.dest;
Cost cost = edge.cost;
Cost addCost = Cost.add(cost, vertex.cost);
if (next.cost.compareTo(addCost) > 0) {
next.cost = addCost;
next.pre = vertex;
pq.add(new Path(next, addCost));
}
}
}
}
public Cost getCost(String destName) {
Vertex end = vertexMap.get(destName);
return end.cost;
}
private Vertex getVertex(String vertexName) {
Vertex vertex = vertexMap.get(vertexName);
if (vertex == null) {
vertex = new Vertex(vertexName);
vertexMap.put(vertexName, vertex);
}
return vertex;
}
private void clearAll() {
for (Vertex v : vertexMap.values()) {
v.reset();
}
}
public List<String> getPath(String startName, String destName) {
List<String> pathList = new LinkedList<String>();
pathList.add(destName);
Vertex destVertex = vertexMap.get(destName);
while (!destVertex.name.equals(startName)) {
pathList.add(0, destVertex.pre.name);
destVertex = destVertex.pre;
}
return pathList;
}
public class Edge {
public Vertex dest;
public Cost cost;
public Edge(Vertex dest, int length, int money) {
cost = new Cost(length, money);
this.dest = dest;
}
public Edge(Vertex dest, Cost cost) {
this.dest = dest;
this.cost = cost;
}
public String toString() {
return " dest " + dest.name + cost;
}
}
public class Path implements Comparable<Path> {
public Vertex dest;
public Cost cost;
public Path(Vertex dest, int length, int money) {
cost = new Cost(length, money);
this.dest = dest;
}
public Path(Vertex dest, Cost cost) {
this.dest = dest;
this.cost = cost;
}
@Override
public int compareTo(Path o) {
return cost.compareTo(o.cost);
}
public String toString() {
return " dest " + dest.name + cost;
}
}
static class Vertex {
public String name;
public List<Edge> adj;
public Cost cost;
public Vertex pre;
public int scratch;
public Vertex(String name) {
this.name = name;
adj = new LinkedList<Edge>();
reset();
}
public void reset() {
cost = INFINITY;
pre = null;
scratch = 0;
}
public String toString() {
return name + cost;
}
}
public static class Cost implements Comparable<Cost>, Cloneable {
public int length;
public int money;
public Cost(int length, int money) {
super();
this.length = length;
this.money = money;
}
public Cost clone() {
return new Cost(length, money);
}
public String toString() {
return " length " + length + " money " + money;
}
@Override
public int compareTo(Cost o) {
if (length < o.length || (length == o.length && money < o.money)) {
return -1;
} else if (length == o.length && money == o.money) {
return 0;
} else {
return 1;
}
}
public static Cost add(Cost cost1, Cost cost2) throws Exception {
int length = cost2.length + cost1.length;
int money = cost2.money + cost1.money;
if (length < 0 || money < 0) {
throw new Exception();
}
Cost addCost = new Cost(length, money);
return addCost;
}
}
}
interface Solution {
Scanner scanner = new Scanner(System.in);
public void input();
public void deal() throws Exception;
public void output();
}
abstract class MiddleSolution implements Solution {
public int[] getIntArray(int count) {
int[] inputArray = new int[count];
for (int i = 0; i < inputArray.length; i++) {
inputArray[i] = scanner.nextInt();
}
return inputArray;
}
public String[] getStringWithSpaceArray(int count) {
String[] inputArray = new String[count];
for (int i = 0; i < inputArray.length; i++) {
inputArray[i] = scanner.nextLine();
}
return inputArray;
}
public String printListWithSpace(List<?> list) {
StringBuilder resultStringBuilder = new StringBuilder();
for (Object object : list) {
resultStringBuilder.append(object + " ");
}
if (resultStringBuilder.length() != 0) {
return resultStringBuilder.substring(0,
resultStringBuilder.length() - 1);
} else {
return "";
}
}
public static String printArrayWithSpace(int[] arr) {
StringBuilder resultStringBuilder = new StringBuilder();
for (int object : arr) {
resultStringBuilder.append(object + " ");
}
if (resultStringBuilder.length() != 0) {
return resultStringBuilder.substring(0,
resultStringBuilder.length() - 1);
} else {
return "";
}
}
}
发表于 2015-12-16 11:50:00
回复(4)
#include<bits/stdc++.h>
using namespace std;
const int Max=510;
const int INF=INT_MAX;
int n,m,s,t;
int dis[Max],c[Max],pre[Max],G[Max][Max],cost[Max][Max];
bool visit[Max];
void Dijistra() {
fill(dis,dis+Max,INF);
fill(c,c+Max,INF);
dis[s]=0;
c[s]=0;
for(int i=0;i<n;i++) pre[i]=i;
for(int i=0; i<n; i++) {
int u=-1,Min=INF;
for(int j=0; j<n; j++) {
if(dis[j]<Min&&!visit[j]) {
Min=dis[j];
u=j;
}
}
if(u==-1) return ;
visit[u]=1;
for(int v=0; v<n; v++) {
if(!visit[v]&&G[u][v]!=INF) {
if(dis[v]>dis[u]+G[u][v]) {
dis[v]=dis[u]+G[u][v];
c[v]=c[u]+cost[u][v];
pre[v]=u;
} else if(dis[v]==dis[u]+G[u][v]&&c[v]>c[u]+cost[u][v]) {
c[v]=c[u]+cost[u][v];
pre[v]=u;
}
}
}
}
}
void DFS(int t) {
if(t==s){
printf("%d ",t);
return ;
}
DFS(pre[t]);
printf("%d ",t);
}
int main() {
scanf("%d %d %d %d",&n,&m,&s,&t);
int from,to;
fill(G[0],G[0]+Max*Max,INF);
for(int i=0; i<m; i++) {
scanf("%d %d",&from,&to);
scanf("%d %d",&G[from][to],&cost[from][to]);
G[to][from]=G[from][to];
cost[to][from]=cost[from][to];
}
Dijistra();
DFS(t);
printf("%d %d\n",dis[t],c[t]);
return 0;
}
发表于 2022-11-29 20:24:46
回复(1)
#include <iostream>
#include<vector>
using namespace std;
int N, M, s, d;
int dstance[500][500], cost[500][500],mindis[500],mincost;
vector<int>b[500],path,minpath;
void dfs(int curcity,int curdis,int curcost)
{
int flag = 0;
if (curdis > mindis[curcity])
{
path.pop_back();
return;
}
else if (curdis == mindis[curcity])
flag = 1;
else
mindis[curcity] = curdis;
//到达目的地
if (curcity == d)
{
if (curcost < mincost&& flag)
{
mincost = curcost;
minpath.assign(path.begin(), path.end());
}
if (flag == 0)
{
mincost = curcost;
minpath.assign(path.begin(), path.end());
}
path.pop_back();
return;
}
else
{
for (int i = 0; i < b[curcity].size(); i++)
{
path.emplace_back(b[curcity][i]);
dfs(b[curcity][i], curdis + dstance[curcity][b[curcity][i]], curcost + cost[curcity][b[curcity][i]]);
}
}
path.pop_back();
return;
}
int main()
{
cin >> N >> M >> s >> d;
mincost = 100000000;
for (int i = 0; i < N; i++)
mindis[i] = 100000000;
for (int i = 0; i < M; i++)
{
int s1, d1, dis, cos;
cin >> s1 >> d1 >> dis >> cos;
b[s1].emplace_back(d1);
b[d1].emplace_back(s1);
dstance[s1][d1] = dis;
dstance[d1][s1] = dis;
cost[s1][d1] = cos;
cost[d1][s1] = cos;
}
//将起点加进去
path.emplace_back(s);
dfs(s, 0, 0);
int flag = 1;
for (int i = 0; i < minpath.size(); i++)
{
if (flag)
{
cout << minpath[i];
flag = 0;
}
else
cout << ' ' << minpath[i];
}
cout << ' ' << mindis[d] << ' ' << mincost;
return 0;
}
发表于 2021-01-22 15:57:19
回复(1)
//Travel Plan (30分)
#include <iostream>
(720)#include <vector>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, start, destination;
int map[1024][1024], charge[1024][1024];
int vis[1024], dis[1024], MIN = INF;
vector<int> path[1024], temppath, realpathh;
void dijk(int city) {
memset(dis, INF, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[city] = 0;
while (true) {
int min = INF, index = -1;
for (int i = 0; i < n; i++) {
if (dis[i] < min && vis[i] != 1) {
min = dis[i];
index = i;
}
}
if (index == -1) break;
vis[index] = 1;
for (int i = 0; i < n; i++) {
if (vis[i] != 1) {
if (dis[i] > dis[index] + map[index][i]) {
dis[i] = dis[index] + map[index][i];
path[i].clear();
path[i].push_back(index);
} else if (dis[i] == dis[index] + map[index][i]) {
path[i].push_back(index);
}
}
}
}
}
void dfs(int index) {
temppath.push_back(index);
if (index == start) {
int sum = 0;
for (int i = 1; i < temppath.size(); i++)
sum += charge[temppath[i]][temppath[i - 1]];
if (sum < MIN) {
realpathh = temppath;
MIN = sum;
}
}
for (int i = 0; i < path[index].size(); i++)
dfs(path[index][i]);
temppath.pop_back();
}
int main() {
cin >> n >> m >> start >> destination;
memset(map, INF, sizeof(map));
memset(charge, 0, sizeof(charge));
for (int i = 0; i < m; i++) {
int x, y, distance, cha;
cin >> x >> y >> distance >> cha;
map[x][y] = map[y][x] = distance;
charge[x][y] = charge[y][x] = cha;
}
dijk(start);
dfs(destination);
for (vector<int>::reverse_iterator it = realpathh.rbegin(); it != realpathh.rend(); it++)
cout << *it << " ";
cout << dis[destination] << " " << MIN;
}
发表于 2020-02-21 17:10:52
回复(0)
a = list(map(int,input().split()))
d = {};m = tuple(sorted((a[2],a[3])))
for i in range(a[1]):
b = list(map(int,input().split()))
c = tuple(sorted([b[0],b[1]]))
if c not in d&nbs***bsp;d[c] > (b[2],b[3]):d[c] = (b[2],b[3])
n = list(d.keys())
for i in range(len(n)):
for j in range(len(n)):
if i - j and set(n[i]) & set(n[j]):
p = tuple(sorted(set(n[i]) ^ set(n[j])))
q = tuple(set(n[i]) & set(n[j]))
r = (d[n[i]][0] + d[n[j]][0],d[n[i]][1] + d[n[j]][1])
if p not in d&nbs***bsp;d[p] > r:
d[p] = r + q
x = [str(a[2])]
x.extend(list(map(str,d[m][2:])))
x.extend(list(map(str,d[m][2:],[a[3],d[m][0],d[m][1]])))
print(' '.join(x)) 平心而论，这题牛客上的用例比pta上的要严谨点，牛客上我一个没过（手动捂脸）
发表于 2020-02-13 14:04:31
回复(0)
此题主要是利用迪杰斯特拉的最短路径算法，每个费用是代表路的费用，所以用二维矩阵存储费用，根据最短路径的类似，可以得到费用也需要一个从起点到某点的最小费用数组，那个记录前驱的我没想到，这个是参考relaxing大佬的，用一个数组记录，下表代表当前节点，值代表前驱节点
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<map>
#define N 510
#define INF 65536
using namespace std;
void shortpath_dij(int start);
void print(int v);
int g[N][N], citys = 0, road = 0, start = 0, destin = 0, D[N], cost[N][N], fee[N],pre[N];//记录从开始节点到最小节点的费用
bool vis[N] = { false };//访问数组
vector p[N];
int main() {
fill(g[0], g[0] + N * N, INF);
fill(cost[0], cost[0] + N * N, INF);
fill(D, D + N, INF);
fill(vis, vis + N, false);
cin >> citys >> road >> start >> destin;
for (int i = 0,x = 0,y = 0,fee = 0; i < road; i++) {
cin >> x >> y;
cin>>g[x][y] >> fee;
g[y][x] = g[x][y];//无向图
cost[x][y] = cost[y][x] = fee;
}
shortpath_dij(start);
print(destin);
cout <<D[destin]<<" "<<fee[destin]<< endl;
system("pause");
return 0;
}
void print(int v) {
if (v == start) {
cout << v << " ";
return;
}
print(pre[v]);
cout << v<<" ";
}
void shortpath_dij(int start) {
int u = 0,v = INF;
D[start] = 0;
fee[start] = 0;
for (int i = 0; i < citys; i++) {
u = 0; v = INF;
for (int i = 0; i < citys; i++) {//找出从开始到未访问最短的节点
if (!vis[i] && D[i] < v) {
v = D[i];
u = i;
}
}
vis[u] = true;
for (int i = 0; i < citys; i++) {
if (!vis[i] && g[u][i] != INF) {
if (D[u] + g[u][i] < D[i]) {
D[i] = D[u] + g[u][i];
fee[i] = fee[u] + cost[u][i];
pre[i] = u;//表示v的前去是u
}
else if (D[u] + g[u][i] == D[i]) {
if (fee[i] > fee[u] + cost[u][i]) {
D[i] = D[u] + g[u][i];
fee[i] = fee[u] + cost[u][i];
pre[i] = u;//表示v的前去是u
}
}
}
}
}
}
编辑于 2019-10-10 22:33:31
回复(0)
//跟public bike那题几乎一样
//PAT和牛客都能过
#include <iostream>
#include <vector>
using namespace std;
//1030 Travel Plan
#define maxn 1e6
vector<int> bestpath;
int bestcost = maxn;
int bestdist = 0;
int cost[500][500] = {};
int g[500][500] = {};
int dist[500] = {};
void dfs(int s, int d, vector<int> path, vector<int> *pre) {
//从s出发回溯至d
if (s == d) {
path.push_back(s);
//到达点d，回溯cost
int cos = 0, dis = 0;
for (int i = path.size() - 1; i > 0; --i) {
cos += cost[path[i]][path[i - 1]];//别写成+=cost[i][i - 1]
dis += g[path[i]][path[i - 1]];
}
if (cos < bestcost) {
bestcost = cos;
bestdist = dis;
bestpath = path;
}
return;
}
//还未抵达d
path.push_back(s);
for (unsigned int i = 0; i < pre[s].size(); ++i) {
dfs(pre[s][i], d, path, pre);
}
path.pop_back();
}
int main() {
int n, m, s, d;//n<=500，城市下标[0,n-1]
int visited[500] = {};
vector<int> pre[500];
cin >> n >> m >> s >> d;
//初始化图
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = maxn;
g[j][i] = maxn;
}
}
//输入
int x, y, dis, cos;
for (int i = 0; i < m; ++i) {
cin >> x >> y >> dis >> cos;
g[x][y] = dis;
g[y][x] = dis;
cost[x][y] = cos;
cost[y][x] = cos;
}
//初始化dist
for (int i = 0; i < n; ++i) {
dist[i] = g[s][i];
}
//小迪
dist[s] = 0;
int k = 0, mindist = maxn;
for (int i = 0; i < n; ++i) {
mindist = maxn;
for (int j = 0; j < n; ++j) {
if (!visited[j] && dist[j] < mindist) {
k = j;
mindist = dist[j];
}
}
visited[k] = 1;
for (int w = 0; w < n; ++w) {
if (!visited[w] && g[k][w] < maxn) {
if (dist[k] + g[k][w] < dist[w]) {
dist[w] = dist[k] + g[k][w];
pre[w].clear();
pre[w].push_back(k);
}
else if (dist[k] + g[k][w] == dist[w]) {
pre[w].push_back(k);
}
}
}
}//end-dijkstra
vector<int> temp;
dfs(d, s, temp, pre);
for (int i = bestpath.size() - 1; i >= 0; --i) {
cout << bestpath[i] << " ";
}
cout << bestdist << " " << bestcost;
return 0;
}
//PAT和牛客都能过
#include <iostream>
#include <vector>
using namespace std;
//1030 Travel Plan
#define maxn 1e6
vector<int> bestpath;
int bestcost = maxn;
int bestdist = 0;
int cost[500][500] = {};
int g[500][500] = {};
int dist[500] = {};
void dfs(int s, int d, vector<int> path, vector<int> *pre) {
//从s出发回溯至d
if (s == d) {
path.push_back(s);
//到达点d，回溯cost
int cos = 0, dis = 0;
for (int i = path.size() - 1; i > 0; --i) {
cos += cost[path[i]][path[i - 1]];//别写成+=cost[i][i - 1]
dis += g[path[i]][path[i - 1]];
}
if (cos < bestcost) {
bestcost = cos;
bestdist = dis;
bestpath = path;
}
return;
}
//还未抵达d
path.push_back(s);
for (unsigned int i = 0; i < pre[s].size(); ++i) {
dfs(pre[s][i], d, path, pre);
}
path.pop_back();
}
int main() {
int n, m, s, d;//n<=500，城市下标[0,n-1]
int visited[500] = {};
vector<int> pre[500];
cin >> n >> m >> s >> d;
//初始化图
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = maxn;
g[j][i] = maxn;
}
}
//输入
int x, y, dis, cos;
for (int i = 0; i < m; ++i) {
cin >> x >> y >> dis >> cos;
g[x][y] = dis;
g[y][x] = dis;
cost[x][y] = cos;
cost[y][x] = cos;
}
//初始化dist
for (int i = 0; i < n; ++i) {
dist[i] = g[s][i];
}
//小迪
dist[s] = 0;
int k = 0, mindist = maxn;
for (int i = 0; i < n; ++i) {
mindist = maxn;
for (int j = 0; j < n; ++j) {
if (!visited[j] && dist[j] < mindist) {
k = j;
mindist = dist[j];
}
}
visited[k] = 1;
for (int w = 0; w < n; ++w) {
if (!visited[w] && g[k][w] < maxn) {
if (dist[k] + g[k][w] < dist[w]) {
dist[w] = dist[k] + g[k][w];
pre[w].clear();
pre[w].push_back(k);
}
else if (dist[k] + g[k][w] == dist[w]) {
pre[w].push_back(k);
}
}
}
}//end-dijkstra
vector<int> temp;
dfs(d, s, temp, pre);
for (int i = bestpath.size() - 1; i >= 0; --i) {
cout << bestpath[i] << " ";
}
cout << bestdist << " " << bestcost;
return 0;
}
编辑于 2019-02-04 23:02:31
回复(0)
#include<iostream>#include<vector>#include<stack>using namespace std;vector<int> d(501,9999),visit(501,0),weight(501,9999);int graph[501][501]={0},cost[501][501]={0};int tra[501];void relax(int i,int j){if(d[j]>d[i]+graph[i][j]){d[j]=d[i]+graph[i][j];weight[j]=weight[i]+cost[i][j];tra[j]=i;}else if(d[j]==d[i]+graph[i][j]){if(weight[j]>weight[i]+cost[i][j]){weight[j]=weight[i]+cost[i][j];tra[j]=i;}}}int main(){int n,m,start,end;cin>>n>>m>>start>>end;for(int i=0;i<m;++i){int tmp1,tmp2,tmp3,tmp4;cin>>tmp1>>tmp2>>tmp3>>tmp4;graph[tmp1][tmp2]=tmp3;cost[tmp1][tmp2]=tmp4;graph[tmp2][tmp1]=tmp3;cost[tmp2][tmp1]=tmp4;}d[start]=0;weight[start]=0;for(int i=0;i<n;i++){int min_value=99999,min_flag=-1;for(int j=0;j<n;++j){if(!visit[j]&&d[j]<min_value){min_value=d[j];min_flag=j;}}visit[min_flag]=1;for(int j=0;j<n;j++){if(graph[min_flag][j])relax(min_flag,j);}}int tmp=end;stack<int> res;while(tmp!=start){res.push(tmp);tmp=tra[tmp];}res.push(start);while(!res.empty()){cout<<res.top()<<" ";res.pop();}cout<<d[end]<<" "<<weight[end]<<endl;return 0;}
发表于 2018-11-08 23:03:26
回复(0)
思路： 题目中的目的有三个 一个是路径 一个是最短路径距离 一个是最短消费。
最短 消费和 最短距离其实可以类比的。不算是难点，就是路径的存储于取出。总而言之我做这道题参考了很多
但是路径，不要带着畏惧心理。多看几遍就能看懂的。
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define MAX 99999
struct city
{
int distance;
int cost;
};
void DIJ(vector<int> & final,
vector<int> & distanceDIJ,
int startCity,
int endCity,
int citysNum,
vector<vector<struct city> >& v,
vector<int>& path,
vector<int> & costCitys)
{
distanceDIJ[startCity] = 0; final[startCity] = 1;
costCitys[startCity] = 0;
// 开始主循环 每次求v0到么个点v的最短距离 并加入v到集合S中。
int minDistanceCity;
for (int i = 1; i < citysNum; i++)
{
int min = MAX;
int minCost = MAX;
for (int j = 0; j < citysNum; j++)
{
if (!final[j])// 如果j定点在V-S中
{
// 距离最近的点
if (distanceDIJ[j] < min)
{
minDistanceCity = j;
min = distanceDIJ[j];
minCost = costCitys[j];
}
}
}
final[minDistanceCity] = 1;// 这点已经找过了。
// 更新当前最短路径和距离
for (int j = 0; j < citysNum; j++)
{
// minDistanceCity 是刚加入集合S中的点
// 则以minDistanceCity为中间点 考察dis(s)
// +dis(sj)是否小于 distanceDIJ[j] 如果小于那么久更新。
// 比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) + d(v3-v5) 的和是否小于D[5]
if (!final[j] && (min + v[minDistanceCity][j].distance < distanceDIJ[j]))
{
distanceDIJ[j] = min + v[minDistanceCity][j].distance;
// path[j]记录d[j]暂时最短路径的最后一个中途节点min_num，表明d[j]最后一段从节点min_num到节点.
path[j] = minDistanceCity;// 中间点
costCitys[j] = minCost + v[minDistanceCity][j].cost;
}
else if (!final[j] && (min + v[minDistanceCity][j].distance == distanceDIJ[j]))
{
if (minCost + v[minDistanceCity][j].cost < costCitys[j])
{
path[j] = minDistanceCity;// 中间点
costCitys[j] = minCost + v[minDistanceCity][j].cost;
}
}
}
}
}
int main()
{
//ifstream cin("test.txt");
int n,// n 个 city
m,// m 条 地铁
s,// 起点城市
d;// 终点城市
while (cin >> n)
{
cin >> m >> s >> d;
vector<vector<struct city> > v(n);//邻接矩阵
for (int i = 0; i < v.size(); i++)
{
v[i].resize(n);
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
v[i][j].distance = MAX;
v[i][j].cost = MAX;
}
}
int city1, city2, distance, cost;
for (int i = 0; i < m; i++)
{
cin >> city1 >> city2 >> distance >> cost;
v[city1][city2].distance = distance;
v[city2][city1].distance = distance;
v[city1][city2].cost = cost;
v[city2][city1].cost = cost;
}
vector<int> final(n, 0);// 集合 S 是否已经确定大小
vector<int> distanceDIJ(n, 0);// 保存最短路径长度。
vector<int> costCitys(n, 0);
vector<int> path(n, -1);// path 原先是一张连通图现在我把它改写为 路径图
for (int i = 0; i < n; i++)
{
distanceDIJ[i] = v[s][i].distance;
costCitys[i] = v[s][i].cost;
}
distanceDIJ[s] = 0;
final[s] = 1;
costCitys[s] = 0;
DIJ(final, distanceDIJ, s, d, n, v, path, costCitys);
// 输出
int i, j;
stack<int> q; //由于记录的中途节点是倒序的，所以使用栈（先进后出），获得正序
j = d;
while (path[j] != -1) //如果j有中途节点
{
q.push(j); //将j压入堆
j = path[j]; //将j的前个中途节点赋给j
}
q.push(j);
//printf("%d=>%d, length:%d, path: %d ", s, i, distanceDIJ[i], s);
cout << s << " ";
while (!q.empty()) //先进后出,获得正序
{
printf("%d ", q.top());//打印堆的头节点
q.pop(); //将堆的头节点弹出
}
cout << distanceDIJ[d] << " ";
cout << costCitys[d] << endl;
}
system("pause");
}
发表于 2018-08-17 23:43:18
回复(0)
只有我是在牛客网上正确PAT上错误么。。。
#include <iostream>
#include <stack>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
int dis[500][500];
int cost[500][500];
bool vis[500];
int totaldis[500];
int totalcos[500];
int past[500];
int n, m, s, d;
stack<int> path;
void dijsktra(int cur)
{
if (vis[cur] || totaldis[cur] >= INF)
{
return;
}
vis[cur] = true;
int mymin = INF;
int mymincos = INF;
int mind = 0;
for (int i = 0; i < n; i++)
{
if (!vis[i])
{
if (totaldis[i] > dis[cur][i] + totaldis[cur])
{
totaldis[i] = dis[cur][i] + totaldis[cur];
totalcos[i] = cost[cur][i] + totalcos[cur];
past[i] = cur;
}
else if (totaldis[i] == dis[cur][i] + totaldis[cur])
{
if (totalcos[i] > cost[cur][i] + totalcos[cur])
{
totaldis[i] = dis[cur][i] + totaldis[cur];
totalcos[i] = cost[cur][i] + totalcos[cur];
past[i] = cur;
}
}
if (totaldis[i] < mymin || (totaldis[i] == mymin && totalcos[i] < mymincos))
{
mymin = totaldis[i];
mind = i;
mymincos = totalcos[i];
}
}
}
dijsktra(mind);
}
int main()
{
memset(dis, 0x3f, sizeof(dis));
memset(cost, 0x3f, sizeof(cost));
memset(vis, 0, sizeof(vis));
memset(totaldis, 0x3f, sizeof(totaldis));
memset(totalcos, 0x3f, sizeof(totalcos));
memset(past, 0x3f, sizeof(past));
cin >> n >> m >> s >> d;
int cur = s;
totaldis[cur] = 0;
totalcos[cur] = 0;
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
cin >> dis[a][b];
cin >> cost[a][b];
dis[b][a] = dis[a][b];
cost[b][a] = dis[b][a];
}
dijsktra(cur);
int temp = d;
while (temp != s && temp < INF)
{
path.push(past[temp]);
temp = past[temp];
}
while (!path.empty())
{
cout << path.top() << " ";
path.pop();
}
cout<<d<<" ";
cout << totaldis[d] << " " << totalcos[d] << endl;
return 0;
}
PAT上是全错的，牛客倒是全对。。。。
发表于 2018-02-22 14:10:18
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
vector<int> min_path, visited;
int min_dist=INT_MAX, min_cost=INT_MAX;
void find(int cur, int dest, int cur_dist, int cur_cost, vector<int> &path, vector<vector<int>> &dist, vector<vector<int>> &cost){
if(cur==dest){
if(cur_dist<min_dist || cur_dist==min_dist && cur_cost<min_cost){
min_path = path;
min_dist=cur_dist, min_cost=cur_cost;
}
return;
}
for(int i=0; i<dist.size(); ++i){
if(visited[i]==0 && dist[cur][i]<INT_MAX){
visited[i] = 1;
path.push_back(i);
find(i, dest, cur_dist+dist[cur][i], cur_cost+cost[cur][i], path, dist, cost);
visited[i] = 0;
path.pop_back();
}
}
return;
}
int main(){
int N,M,S,D;
cin>>N>>M>>S>>D;
vector<vector<int>> dist(N, vector<int>(N,INT_MAX)), cost(N, vector<int>(N,INT_MAX));
for(int i=0; i<M; ++i){
int c1, c2, dis, cos;
cin>>c1>>c2>>dis>>cos;
if(dist[c1][c2]>dis || dist[c1][c2]==dis && cost[c1][c2]>cos){
dist[c1][c2] = dist[c2][c1] = dis;
cost[c1][c2] = cost[c2][c1] = cos;
}
}
for(int i=0; i<N; ++i) visited.push_back(0);
vector<int> path;
path.push_back(S);
find(S,D,0,0,path,dist,cost);
for(int i=0; i<min_path.size(); ++i){
cout<<min_path[i]<<" ";
}
cout<<min_dist<<" "<<min_cost<<endl;
return 0;
}
编辑于 2018-02-13 20:00:02
回复(0)
问题信息
难度：
26条回答
13收藏
11501浏览
通过挑战的用户
-
2023-03-09 15:18:11 -
2023-02-21 10:34:49 -
2023-02-18 21:42:44 -
2023-02-16 20:33:56
-
2023-02-04 00:42:34
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
