Emergency (25)_

JacobGo！

第一次做图的题，写了两个上午啊。思路：用dijkstra+dfs

很奇怪，牛客通过率是90%，最后提示的是内存超限。但是在PAT网站可以完全通过

附上PAT测试网址：https://www.patest.cn/submissions/3481872

不过，如果要在PAT提交，注意的是，PAT不支持备注，请手动删除。。。。巨崩溃

 import java.util.Scanner;

/**
 * Emergency (25)
 * 
 * @author Administrator 牛客通过率只有90%
 */
public class Main {
	static int[][] map; // 邻接矩阵，存储所有边
	static boolean[] visited; // 标志一个城市是否已经被访问
	static int[] dist; // 记录从起点到某点的距离。初始化为Integer.MAX_VALUE
	static int[] cityTeams;// 记录每个城市的救援队数量
	static int maxTeams;// 记录到达每个城市最大救援队数量
	static int count; // 记录最短路径数
	static int source;// 起点
	static int dest;// 重点
	static int cityNum;// 城市数量

	public static void main(String[] args) {
		// 初始化
		Scanner sc = new Scanner(System.in);
		cityNum = sc.nextInt();
		int edgeNum = sc.nextInt();
		source = sc.nextInt();
		dest = sc.nextInt();

		map = new int[cityNum][cityNum];
		visited = new boolean[cityNum];
		dist = new int[cityNum];
		cityTeams = new int[cityNum];
		for (int i = 0; i < cityNum; i++) {
			cityTeams[i] = sc.nextInt();
		}
		for (int i = 0; i < cityNum; i++) {
			dist[i] = Integer.MAX_VALUE;
			for (int j = 0; j < cityNum; j++) {
				if (i == j)
					map[i][i] = 0;
				else
					map[i][j] = Integer.MAX_VALUE;
			}
		}
		// 边初始化
		for (int i = 0; i < edgeNum; i++) {
			int a = sc.nextInt(), b = sc.nextInt(), L = sc.nextInt();
			map[a][b] = L;
			map[b][a] = L;
		}
		sc.close();
		dijkstra(source, dest, cityNum);
		for (int i = 0; i < cityNum; i++)
			visited[i] = false;
		dfs(source, cityTeams[source]);
		System.out.println(count + " " + maxTeams);
	}

	private static void dfs(int s, int teamNum) {
		if (s == dest) {
			if (teamNum > maxTeams)
				maxTeams = teamNum;
			count++;
			return;
		}
		visited[s] = true;
		for (int i = 0; i < cityNum; i++) {
			if (!visited[i] && dist[i] == dist[s] + map[s][i]) {
				visited[i] = true;
				dfs(i, teamNum + cityTeams[i]);
				visited[i] = false;
			}
		}
	}

	private static void dijkstra(int source, int dest, int cityNum) {
		// dest = 3;
		dist[source] = 0;
		int curNode = source;
		while (true) {
			// 把当前点加入已遍历集合
			if (curNode == -1)
				break;
			visited[curNode] = true;
			for (int i = 0; i < cityNum; i++) {
				// (map[curNode][i] + dist[curNode] < dist[i])会溢出
				if (!visited[i] && map[curNode][i] <= dist[i] - dist[curNode]) {
					dist[i] = map[curNode][i] + dist[curNode];
				}
			}
			int min = Integer.MAX_VALUE, index = -1;
			// 找到当前未放入已遍历集合的路径最小值
			for (int i = 0; i < cityNum; i++) {
				if (!visited[i] && dist[i] < min) {
					// 如果最小值更新，计数器从0开始重新计数
					min = dist[i];
					index = i;
				}
			}
			curNode = index;
		}
	}
}

编辑于 2017-08-24 11:38:29 回复(1)

Myhui

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=510;
const int INF=10000000;                                               //INF作为“无穷大”即不可能的距离
struct Node{                                                          //边表结点（v为顶点编号，dis为边权值）
    int v,dis;
};
vector<Node> Adj[maxn];
bool vis[maxn]={false};                                               //d为起点到某点最短路径，num为到某点最短路径条数
int n,m,start,final,d[maxn],num[maxn]={0},weight[maxn],w[maxn]={0};   //weight为某点权值，w为到某点最短路径中点权值和最大
void Dijkstra(int s){
    fill(d,d+maxn,INF);d[s]=0;                                        //初始化到各点最短路径长，s为起点，起点到本身路径为0
    num[s]=1;                                                         //到起点本身的最短路径初始为1条
    w[s]=weight[s];                                                   //到起点本身的最短路径点权之和初始即为起点本身权值
    for(int i=0;i<n;i++){
        int u=-1,min=INF;                                             //初始化
        for(int j=0;j<n;j++){                                         //找到未访问过的结点中d[]最小的
            if(vis[j]==false&&d[j]<min){
                u=j;min=d[j];
            }
        }
        if(u==-1) return;                                             //找不到小于INF的d[u],即剩下的结点与起点s不连通                                           
        vis[u]=true;
        for(int j=0;j<Adj[u].size();j++){
            int v=Adj[u][j].v;
            if(vis[v]==false){                                        //若v未访问过
                if(d[u]+Adj[u][j].dis<d[v]){                          //若u作为中介点可以使d[v]更优
                    d[v]=d[u]+Adj[u][j].dis;
                    num[v]=num[u];                                    //覆盖到v的最短路径条数
                    w[v]=w[u]+weight[v];
                }
                else if(d[u]+Adj[u][j].dis==d[v]){                    //找到一条与最短路径相同长度的路径
                    num[v]+=num[u];                                   //直接加上到u的最短路径条数
                    if(w[v]<w[u]+weight[v])                           //若以u为中介点时点权之和更大
                        w[v]=w[u]+weight[v];
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>start>>final;
    for(int i=0;i<n;i++)
        cin>>weight[i];
    for(int i=0;i<m;i++){
        int id1,id2,dis;
        Node temp;
        cin>>id1>>id2>>temp.dis;
        temp.v=id2;Adj[id1].push_back(temp);                          //无向图
        temp.v=id1;Adj[id2].push_back(temp);
    }
    Dijkstra(start);
    cout<<num[final]<<" "<<w[final];
    return 0;
}

发表于 2019-02-04 23:41:34 回复(0)

我才不要当你爸爸

//PAT和牛客都AC了，有疑问可以评论
#include<iostream>
#include<algorithm>
#define inf 65535
using namespace std;
int n,m,s,t,used[500]={0},cost[500][500],mincost[500],path[500],amount[500],maxget[500];
void dijkstra(int s)
{
    int u,v,i,j;
    fill(path,path+500,1);
    mincost[s]=0;
    while(1)
    {
        v=-1;
        for(u=0;u<n;u++)
            if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;
        if(v==-1) break;
        used[v]=1;
        for(u=0;u<n;u++)
        {
            if(!used[u]&&mincost[u]>mincost[v]+cost[v][u])
            {
                mincost[u]=mincost[v]+cost[v][u];
                maxget[u]=maxget[v]+amount[u];
                path[u]=path[v];
            }
            else if(!used[u]&&mincost[u]==mincost[v]+cost[v][u])
            {
                path[u]+=path[v];
                maxget[u]=max(maxget[u],maxget[v]+amount[u]);
            }    
        }
    }
}
int main()
{
    int i,j,u,v;
    for(i=0;i<500;i++)
        for(j=0;j<500;j++)
            cost[i][j]=inf;
    cin>>n>>m>>s>>t;
    for(i=0;i<n;i++)
    {
        mincost[i]=inf;
        cin>>amount[i];
        maxget[i]=amount[i];
    }  
    for(i=0;i<m;i++)
    {
        cin>>u>>v;
        cin>>cost[u][v];
        cost[v][u]=cost[u][v];
    }
    dijkstra(s);
    cout<<path[t]<<' '<<maxget[t];
    return 0;
}

发表于 2018-12-21 16:14:09 回复(0)

determinedcray

我真是服了，这里是正确的，但是pat上测点3过不去，不给测点真是脑壳痛

	#include<iostream>
#include<vector>
using namespace std;
const int maxCity = 510;
const int maxValue = 1000000000;
int cityNum, roadNum, cityStart, cityEnd;
int teamAmount[maxCity];
struct Node
{
 int number;
 int value = maxValue;
 Node(int number, int value)
 {
  this->number = number;
  this->value = value;
 }



	};
vector<Node> graph[maxCity];
void stPath(int &pathNumber, int &teamNumber)
{
 pathNumber = 0;
 teamNumber = 0;
 bool isFind[maxCity] = { false };
 int minPath[maxCity] = { maxValue };//记录最短路径
 int minPathNumber[maxCity] = { 0 };//到达某个点最短路径数量
 int maxTeamAmount[maxCity] = { 0 };
 //赋初值
 for (int i = 0; i < cityNum; i++)
 {
  minPath[i] = maxValue;
 }
 minPath[cityStart] = 0;//起始位置置0；
 int pathThrough = cityStart;//代表中间节点
 isFind[cityStart] = true;
 minPathNumber[cityStart] = 1;//防止更新后永远为0；
 maxTeamAmount[cityStart] = teamAmount[cityStart];
 for (int i = 0; i < cityNum - 1; i++)//外层循环结束时所有最小路径找到
 {
  //更新所有节点
  for (auto iter = graph[pathThrough].begin(); iter != graph[pathThrough].end(); iter++)
  {
   if (isFind[iter->number] == false)
   {
    if (iter->value + minPath[pathThrough] < minPath[iter->number])//如果经过中间节点可以更短，则更新最小值和路径数量
    {
     minPath[iter->number] = iter->value + minPath[pathThrough];
     minPathNumber[iter->number] = minPathNumber[pathThrough];
     maxTeamAmount[iter->number] = maxTeamAmount[pathThrough] + teamAmount[iter->number];//更新团队数量
    }
    else if (iter->value + minPath[pathThrough] == minPath[iter->number])
    {
     minPathNumber[iter->number]++;
     if (maxTeamAmount[pathThrough] + teamAmount[iter->number] > maxTeamAmount[iter->number])
     {
      maxTeamAmount[iter->number] = maxTeamAmount[pathThrough] + teamAmount[iter->number];
     }
    }
   }
  }
  //更新完后寻找一个最小节点作为新的经过点
  int min = maxValue + 10;
  int index;
  for (int j = 0; j < cityNum; j++)
  {
   if (isFind[j] == false && minPath[j] < min)
   {
    index = j;
    min = minPath[j];
   }
  }
  pathThrough = index;
  isFind[index] = true;
 }
 pathNumber = minPathNumber[cityEnd];
 teamNumber = maxTeamAmount[cityEnd];
}
int main()
{
 //输入
 cin >> cityNum >> roadNum >> cityStart >> cityEnd;
 for (int i = 0; i < cityNum; i++)
 {
  cin >> teamAmount[i];
 }
 for (int i = 0; i < roadNum; i++)
 {
  int c1, c2, length;
  cin >> c1 >> c2 >> length;
  graph[c1].push_back(Node(c2, length));
  graph[c2].push_back(Node(c1, length));
 }
 int pathNumber, teamNumber;
 stPath(pathNumber, teamNumber);
 cout << pathNumber << ' ' << teamNumber;
 return 0;
}

发表于 2018-10-14 20:42:59 回复(0)

Rullec

/*因为初学，被这道题目卡了一会，也好好研究了一下图论里的常用算法。

把自己的代码做了比较详细的注释，贴出来，很多不足的地方，还望大家批评指正。

基本的思路就是从终点的dijkstra，以及从源点出发的一个经过部分改良的DFS

dijkstra的作用是得到最短路径的长度，以及图中各点到终点的最短距离，这在dfs中的递归判断条件中用的到。

整道题目最精髓的地方我认为是dfs中的判断条件~希望对大家有提示作用
*/

#include <iostream>

#include <algorithm>

#define Inf 65535

using namespace std;

/*dijkstra算法需要的*/

int dist[501];//这个结点到源点的距离

int Graph[501][501];//图的邻接矩阵实现

/*dfs需要的*/

int Team[501];//各个城市中的队伍数目

bool visited[501];//是否访问过这个结点

/*全局变量*/

int VNum;//vertex num 即城市个数

int NumMinst;//最短路的个数

int Peo;//能纠集起来的最多的队伍数

int src, goal;//出发点和目的地

void dijkstra(int s);

void dfs(int s, int peo);

void init();

int FindMin();

int main()

{

/*初始化*/

int ENum;//边数

cin >> VNum >> ENum >> src >> goal;

/*初始化*/

init();

for (int i = 0; i < VNum; i++)

cin >> Team[i];

int x, y, wei;

for (int i = 0; i < ENum; i++)

{

cin >> x >> y >> wei;

/*若存在负值圈*/

if (wei < 0)

{

cout << 0;

return 0;

}

Graph[x][y] = Graph[y][x] = wei;//此处是无向图这么写

}

/*使用dijk算法填充dist数组并藉此得到最短路径条数*/

dijkstra(goal);

for (int i = 0; i < VNum; i++)

visited[i] = 0;

/*把源点收入*/

visited[src] = 1;

/*开始dfs搜索*/

dfs(src, Team[src]);

cout << NumMinst << " " << Peo;

return 0;

}

void init()

{

for (int i = 0; i < VNum; i++)

{

for (int j = 0; j < VNum; j++)

{

if (i == j)

Graph[i][i] = 0;

else

Graph[i][j] = Inf;

}

dist[i] = Inf;

}

void dijkstra(int s)

{

/*先收入源点*/

visited[s] = true;

dist[s] = 0;

/*更新一下源点的邻接点的dist*/

for (int i = 0; i < VNum; i++)

{

if (!visited[i] && Graph[s][i] < Inf)

dist[i] = Graph[s][i];

}

while (1)

{

int v = FindMin();

/*v==-1说明算法结束*/

if (v == -1)

break;

/*收入该结点*/

visited[v] = true;

for (int i = 0; i < VNum; i++)

{

if (dist[i] > dist[v] + Graph[v][i])

dist[i] = dist[v] + Graph[v][i];

}

int FindMin()//寻找此时dist[]数组中，dist[i]最小的结点

{

int Minst = Inf;

int IdMin = -1;

for (int i = 0; i < VNum; i++)

{

if (!visited[i]&&dist[i] < Minst)

{

Minst = dist[i];

IdMin = i;

}

return IdMin;

}

void dfs(int s, int peo)

{

/*dfs的形式是递归所以要先写终止条件*/

if (s == goal)//如果到达终点

{

if (peo > Peo)

Peo = peo;//更新能纠集的最大人数

NumMinst++;//最短路条数+1

return;

}

/*对于所有结点来说*/

for (int i = 0; i < VNum; i++)

{

/*如果这个结点，没有被访问过，而且是最短路径上的结点。P.S.这个判断是精髓，好好理解*/

if (!visited[i] && dist[i] == dist[s] - Graph[s][i])

{

visited[i] = 1;

dfs(i, peo + Team[i]);

/*注意下面的visited[i] = 0，是一个恢复的过程，也是和一般的dfs不同的地方

很重要，不执行的话将无法找到多条最短路。类似栈的概念*/

visited[i] = 0;

}

发表于 2016-07-31 11:05:06 回复(2)

Python

初心者托奇

a = list(map(int,input().split()))
weight = list(map(int,input().split()))             # 点权
G = [[1000000000] * a[0] for j in range(a[0])]      # 邻接矩阵
for i in range(a[1]):
    c = list(map(int,input().split()))
    G[c[0]][c[1]],G[c[1]][c[0]] = c[2],c[2]
d = [1000000000] * a[0]                             # 最短距离
num = [0] * a[0]                                    # 最短路径条数
w = [0] * a[0]                                      # 最大点权和
vis = [1] * a[0]                                    # 是否访问过
d[a[2]] = 0
w[a[2]] = weight[a[2]]
num[a[2]] = 1

while True:
    u,MIN = -1,1000000000
    for j in range(a[0]):
        if vis[j] and d[j] < MIN:
            u,MIN = j,d[j]
    if u == -1:                                     # 全访问完或不可达
        break
    vis[u] = 0
    
    for v in range(a[0]):
        if(vis[v] and G[u][v] != 1000000000):       # 未曾访问且可达
            if d[u] + G[u][v] < d[v]:               # 如果距离更短
                d[v] = d[u] + G[u][v]
                w[v] = w[u] + weight[v]
                num[v] = num[u]
            elif d[u] + G[u][v] == d[v]:            # 如果权值更大
                if w[u] + weight[v] > w[v]:
                    w[v] = w[u] + weight[v]
                num[v] += num[u]

print(num[a[3]],w[a[3]])

核心就是Dijkstra算法了，用对了就很快。

编辑于 2020-07-13 11:09:46 回复(0)

Java

liyuchang

java版。Dijkstra求source 到各顶点的最短距离/条数/累计人数最多（点权）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Dijkstra求source 到各顶点的最短距离/条数/累计人数最多（点权）
 */
public class Main {
	// 顶点数
	private static int num;
	// 图
	private static int[][] g;
	// 顶点是否已访问
	private static boolean[] v;
	// 顶点s到各顶点的最短路径长度
	private static int[] d;
	// 顶点s到各顶点的最短路的条数
	private static int[] count;
	// 各顶点人数
	private static int[] p;
	// 顶点s到各顶点的路径累计人数
	private static int[] sum;
	// 顶点s到各顶点的最短路径初始值（极大值）
	private static int INF = 1_000_000_000;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String line1 = bf.readLine();
		String[] lineas1 = line1.split(" ");
		num = Integer.valueOf(lineas1[0]);
		int roads = Integer.valueOf(lineas1[1]);
		int source = Integer.valueOf(lineas1[2]);
		int destination = Integer.valueOf(lineas1[3]);
		String line2 = bf.readLine();
		String[] lineas2 = line2.split(" ");
		p = new int[num];
		// 初始化各顶点人数
		for (int i = 0; i < num; i++) {
			p[i] = Integer.valueOf(lineas2[i]);
		}
		// 初始化顶点s到各顶点的路径累计人数
		sum = new int[num];
		sum[source] = p[source];
		// 初始化图
		g = new int[num][num];
		while (roads-- > 0) {
			String line = bf.readLine();
			String[] lineas = line.split(" ");
			int i = Integer.valueOf(lineas[0]);
			int j = Integer.valueOf(lineas[1]);
			int length = Integer.valueOf(lineas[2]);
			g[i][j] = length;
			g[j][i] = length;
		}
		bf.close();
		// 初始化顶点source到各顶点的路径
		d = new int[num];
		count = new int[num];
		for (int i = 0; i < num; i++) {
			if (i == source) {
				d[i] = 0;
				count[i] = 1;
			} else {
				d[i] = INF;
			}
		}
		v = new boolean[num];
		// Dijsktra
		int nums = num;
		while (nums-- > 0) {
			int u = minAndNotVisited(d, v);
			if (u == -1){
				break;
			}
			v[u] = true;
			// 更新从source出发经u到u相连的顶点v的距离/最短路径条数/累计人数
			for (int j = 0; j < num; j++) {
				if (g[u][j] > 0 && !v[j]) {
					if(d[u] + g[u][j] < d[j]) {
						d[j] = d[u] + g[u][j];
						count[j] = count[u];
						sum[j] = sum[u] + p[j];
					} else if (d[u] + g[u][j] == d[j]) {
						count[j] = count[u] + count[j];
						if((sum[u] + p[j])>sum[j]) {
							sum[j] = sum[u] + p[j];
						}
					}
				}
			}
		}
		System.out.print(count[destination]+" "+sum[destination]);

	}

	/**
	 * 获取未访问过且离source最近的顶点u,返回-1说明找不到和source相连接的且未访问过的顶点
	 */
	private static int minAndNotVisited(int[] d, boolean[] v) {
		int u = -1; int min = INF;
		for (int i = 0; i < num; i++) {
			if (d[i] < min && !v[i]) {
				u = i;
				min = d[i];
			}
		}
		return u;
	}
}

发表于 2019-10-23 12:30:59 回复(0)

C/C++

叮哩当啷

//过了pat和牛客所有用例
#include <iostream>
using namespace std;
const int maxn=501,INF=1000000000;
int n,g[maxn][maxn],d[maxn],weight[maxn],w[maxn],num[maxn];
bool visited[maxn]={false};
void dijkstra(int s)
{
    int min,u;
    fill(d,d+maxn,INF);
    fill(w,w+maxn,0);
    fill(num,num+maxn,0);
    d[s]=0;
    w[s]=weight[s];
    num[s]=1;
    for(int i=0;i<n;i++)
    {
        min=INF;
        for(int j=0;j<n;j++)
        {
            if(visited[j]==false&&d[j]<min)
            {
                u=j;
                min=d[j];
            }
        }
        visited[u]=true;
        for(int v=0;v<n;v++)
        {
            if(visited[v]==false&&g[u][v]!=INF)
            {
                if(d[u]+g[u][v]<d[v])
                {
                    d[v]=d[u]+g[u][v];
                    w[v]=w[u]+weight[v];
                    num[v]=num[u];
                }
                else if(d[u]+g[u][v]==d[v])//只在路径长度相等的情况下，选择点权最大的
                {
                    num[v]+=num[u];
                    if(w[v]<w[u]+weight[v])
                        w[v]=w[u]+weight[v];
                }     
            }
        }
    }
}

int main() 
{
    int edge,u,v,start,end;
    cin>>n>>edge>>start>>end;
    fill(g[0],g[0]+maxn*maxn,INF);
    for(int i=0;i<n;i++)
        cin>>weight[i];
    for(int i=0;i<edge;i++)
    {
        cin>>u>>v;
        cin>>g[u][v];
        g[v][u]=g[u][v];
    }
    dijkstra(start);
    cout<<num[end]<<" "<<w[end]<<endl;;
}

发表于 2018-03-01 15:26:24 回复(0)

巴黎的夜雪灬寂静的空城

#include<stdio.h>
#include<vector>
using namespace std;
struct way{
	int next;
	int w;
};
vector<way> E[504];
int han[504];
bool mark[504];
int Dis[504];
int Han[504];
//在dijkstra基础上加Han数组记录到达对应城市能得到的最大帮手 
int main()
{
	int n,m,c1,c2;
	while( scanf("%d%d%d%d",&n,&m,&c1,&c2)!= EOF )
	{
		for( int i = 0 ; i < n  ; i++ )
		{
			E[i].clear();
			Dis[i] = Han[i] = -1;
			mark[i] = false;
		}
		for( int i = 0 ; i < n ; i++ )
		scanf("%d",&han[i]);
		
		//存储双向边 
		for( int i = 0 ; i < m ; i++ )
		{
			int x,y,c;
			scanf("%d%d%d",&x,&y,&c);
			struct way s;
			s.next = y;
			s.w = c;
			E[x].push_back(s);
			s.next = x;
			E[y].push_back(s);
		}
		
		//count记录有几条最短路 
		int count;
		int tmp = c1;
		Dis[c1] = 0;
		Han[c1] = han[c1];
		mark[c1] = true;
		for( int i = 1; i < n ; i++ )
		{
			for( int j = 0 ; j < E[tmp].size() ; j++ )
			{
				int nn = E[tmp][j].next;
				int cc = E[tmp][j].w;
				if( mark[nn] == true )
				continue;
				if( Dis[nn] == -1 || Dis[nn] > Dis[tmp] + cc )
				{
					Dis[nn] = Dis[tmp] + cc;
					Han[nn] = Han[tmp] + han[nn];
					//若位到达目标城市的最短路，则记录 
					if( nn == c2 )
					count = 1;
				}
				else if( Dis[nn] == Dis[tmp] + cc  )
				{
					//又存在一条到达目标城市且等于当前最短路的路径 
					if( nn == c2 )
					count++;
					//比较帮手数目 
					if( Han[nn] < Han[tmp] + han[nn] )
					Han[nn] = Han[tmp] + han[nn];
				}
			}
			int min = 123123123;
			for( int j = 0 ; j < n ; j++ )
			{
				if( mark[j] == true )
				continue;
				if( Dis[j] == -1 )
				continue;
				if( Dis[j] < min )
				{
					min = Dis[j];
					tmp = j;
				}
			}
			mark[tmp] = true;
		}
		printf("%d %d\n",count,Han[c2]);
	}
	return 0;
}

发表于 2019-09-11 15:37:38 回复(0)

LiuTaw

没有用高大上的算法，直接DFS（思路简单），但是牛客网提示60%通过，后面超时了，PAT上面只有一个测试没通过，想不通啊，求大神解答

思路：首先用邻接表建立图，然后直接深度优先遍历，找出所有从c1到c2遍历的路径，计算所有的最短路径的条数和最大救援队的数量。需要注意的是，每次要标记已经访问过的结点，已经访问的不要再访问了，在当次遍历中还要恢复标记的，下次遍历再访问，这个是个易错点，如果设置成全局的，那么会少很多遍历，自己卡了很久，大家注意～

#include<stdio.h>

#include<iostream>

#include<vector>

using namespace std;

struct Edge

{

int nextIndex,cost;

Edge(int a,int b)

{

this->nextIndex = a;

this->cost = b;

}

};

void find(int index,vector<Edge> *vertex,int findIndex,int cost,int rescueTeams,int *teams);

int already[100] ={false};

int minCost = 10000;

int maxResTeams = 0;

int differRoads = 0;

int main()

{

int N,M,c1,c2;

scanf("%d %d %d %d",&N,&M,&c1,&c2);

int *teams = new int[N];

vector<Edge> *vertex = new vector<Edge>[N];

for(int i=0;i<N;i++)

{

scanf("%d",teams+i);

//cout<<*(teams+i)<<endl;

}

//cout<<*(teams+1)<<endl;

for(int i =0;i<M;i++)

{

int a,b,c;

scanf("%d %d %d",&a,&b,&c);

vertex[a].push_back(Edge(b,c));

vertex[b].push_back(Edge(a,c));

//cout<<a<<"-"<<b<<"-"<<c<<endl;

}

////遍历看看是否正确

//for(int i=0;i<N;i++)

//{

// for(int j=0;j<vertex[i].size();j++)

// {

// cout<<"node:"<<i<<"--"<<vertex[i][j].cost<<"--"<<vertex[i][j].nextIndex<<endl;

// }

//}

//遍历找出两点之间的最短路径

already[c1]=true;

find(c1,vertex,c2,0,teams[c1],teams);

cout<<differRoads<<" "<<maxResTeams<<endl;

return 0;

}

void find(int index,vector<Edge> *vertex,int findIndex,int cost,int rescueTeams,int *teams)

{

for(unsigned int i=0;i<vertex[index].size();i++)

{

//找到了

int currentCost = cost+vertex[index][i].cost;

int currentRescuTeams = rescueTeams+teams[vertex[index][i].nextIndex];

//跳过已经访问过的

if(already[vertex[index][i].nextIndex])

continue;

if(vertex[index][i].nextIndex==findIndex)

{

//cout<<"cost-"<<currentCost<<"-"<<currentRescuTeams<<endl;

//已经找到了，就开始记录题目要求记录的

if(minCost>currentCost)

{

minCost = currentCost;

maxResTeams = currentRescuTeams;

differRoads = 1;

}

else if(minCost==currentCost)

{

if(maxResTeams<currentRescuTeams)

maxResTeams = currentRescuTeams;

differRoads++;

}

}else

{

//重要的地方，如何跳过已经找到的！

already[vertex[index][i].nextIndex]=true;

//未找到，继续找

find(vertex[index][i].nextIndex,vertex,findIndex,currentCost,currentRescuTeams,teams);

already[vertex[index][i].nextIndex]=false;

}

编辑于 2018-02-14 21:24:56 回复(2)

JimmyYgest

为啥在PTA上就有三个样例通不过
在牛客上就通过了

发表于 2019-11-13 10:40:59 回复(0)

Java

HackerLzh

import java.util.*;
import java.io.*;


public class Main {
    private static int N, M, C1, C2;
    private static int[][] graph;
    private static int[] teams, dist, routes, rescues;
    private static boolean[] visited;
    private final static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split("\\s+");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        C1 = Integer.parseInt(line[2]);
        C2 = Integer.parseInt(line[3]);
        graph = new int[N][N];
        teams = new int[N];
        dist = new int[N];
        routes = new int[N];
        rescues = new int[N];
        visited = new boolean[N];
        line = br.readLine().split("\\s+");
        for (int i = 0; i < N; ++i) {
            teams[i] = Integer.parseInt(line[i]);
        }
        for (int[] row : graph) {
            Arrays.fill(row, INF);
        }
        for (int i = 0; i < M; ++i) {
            line = br.readLine().split("\\s+");
            int v1 = Integer.parseInt(line[0]);
            int v2 = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            graph[v1][v2] = w;
            graph[v2][v1] = w;
        }
        Arrays.fill(dist, INF);
        dist[C1] = 0;
        routes[C1] = 1;
        rescues[C1] = teams[C1];

        for (int i = 0; i < N; ++i) {
            int u = -1, minDist = INF;
            for (int j = 0; j < N; ++j) {
                if (!visited[j] && dist[j] < minDist) {
                    u = j;
                    minDist = dist[j];
                }
            }
            if (u == -1) {
                break;
            }
            visited[u] = true;
            for (int v = 0; v < N; ++v) {
                if (!visited[v] && graph[u][v] != INF) {
                    if (dist[u] + graph[u][v] < dist[v]) {
                        dist[v] = dist[u] + graph[u][v];
                        routes[v] = routes[u];
                        rescues[v] = rescues[u] + teams[v];
                    } else if (dist[u] + graph[u][v] == dist[v]) {
                        routes[v] += routes[u];
                        if (rescues[u] + teams[v] > rescues[v]) {
                            rescues[v] = rescues[u] + teams[v];
                        }
                    }
                }
            }
        }
        System.out.format("%d %d\n", routes[C2], rescues[C2]);
    }

}

发表于 2025-02-10 13:15:05 回复(0)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

const int Max=510;
const int INF=INT_MAX;
int weight[Max],dis[Max],num[Max],w[Max];
int n,m,s,t;
bool visit[Max];

struct node {
	int to;
	int l;
	node(int a,int b):to(a),l(b) {}
};

vector<node> G[Max];

void Dijistra() {
	fill(dis,dis+Max,INF);
	memset(num,0,sizeof(num));
	memset(w,0,sizeof(w));
	dis[s]=0;
	num[s]=1;
	w[s]=weight[s];
	for(int i=0; i<n; i++) {
		int u=-1,Min=INF;
		for(int j=0; j<n; j++) {
			if(!visit[j]&&dis[j]<Min) {
				Min=dis[j];
				u=j;
			}
		}
		if(u==-1) return ;
		visit[u]=1;
		for(int k=0; k<G[u].size(); k++) {
			int v=G[u][k].to;
			if(!visit[v]) {
				if(dis[u]+G[u][k].l<dis[v]) {
					dis[v]=dis[u]+G[u][k].l;
					w[v]=w[u]+weight[v];
					num[v]=num[u];
				} else if(dis[u]+G[u][k].l==dis[v]) {
					if(weight[v]+w[u]>w[v]) {
						w[v]=weight[v]+w[u];
					}
					num[v]+=num[u];
				}
			}
		}
	}
}

int main() {
	scanf("%d %d %d %d",&n,&m,&s,&t);
	for(int i=0; i<n; i++) {
		scanf("%d",&weight[i]);
	}
	int from,to,L;
	for(int i=0; i<m; i++) {
		scanf("%d %d %d",&from,&to,&L);
		G[from].emplace_back(node(to,L));
		G[to].emplace_back(node(from,L));
	}
	Dijistra();
	printf("%d %d\n",num[t],w[t]);
	return 0;
}

发表于 2022-11-29 14:20:59 回复(0)

かの

//一开始出错是因为不清楚这是无向图看成有向图了

#include<iostream>

#include<cstring>
using namespace std;
const int N=510;
int g[N][N];
int weight[N],w[N],num[N],dist[N];
int n,m,c1,c2;
bool st[N];

void dijkstra(int u)
{
memset(dist,0x3f,sizeof dist);
memset(w,0,sizeof w);
memset(num,0,sizeof num);
w[u]=weight[u];
num[u]=1;
dist[u]=0;

for(int i=0;i<n;i++)
{
int t=-1;
for(int j=0;j<n;j++)
if(!st[j] && (t==-1 || dist[t]>dist[j]))
t=j;

st[t]=true;

for(int j=0;j<n;j++)
{
if(dist[j]>dist[t]+g[t][j])
{
dist[j]=dist[t]+g[t][j];
num[j]=num[t];
w[j]=w[t]+weight[j];
}
else if(dist[j]==dist[t]+g[t][j])
{
num[j]+=num[t];
if(w[j]<w[t]+weight[j])
w[j]=w[t]+weight[j];
}
}
}

}

int main()
{
scanf("%d%d%d%d",&n,&m,&c1,&c2);
memset(g,0x3f,sizeof g);

for(int i=0;i<n;i++)
scanf("%d",&weight[i]);

while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=min(g[a][b],c);
}

dijkstra(c1);

printf("%d %d\n",num[c2],w[c2]);

return 0;
}

发表于 2022-02-26 10:50:39 回复(0)

Vladivostok

用迪杰斯特拉算法即可。《算法笔记》上这个算法有三种扩展：增加边权，点权和计算几条最短路径。这个题是点权和计算几条最短路径两者的结合。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define INF 100000000
using namespace std;

int n,m,c1,c2;

int num[500];
int tu[500][500];

bool visited[500];
int num_of_luxian[500];
int maxgather[500];
int dis[500];

void dijs(){

    dis[c1] = 0;
    num_of_luxian[c1] = 1;
    maxgather[c1] = num[c1];

    for(int i = 0;i<n;i++){

        int mina = INF,u = -1;
        for(int j = 0;j<n;j++){
            if(visited[j]==false&&dis[j]<mina){
                mina = dis[j];
                u = j;
            }
        }
        if(u==-1){
            return;
        }

        visited[u] = true;
        if(u==c2){
            return;
        }

        for(int j = 0;j<n;j++){
            if(visited[j]==false&&tu[u][j]<INF){
                if(tu[u][j]+dis[u]<dis[j]){
                    dis[j] = tu[u][j]+dis[u];
                    num_of_luxian[j] = num_of_luxian[u];
                    maxgather[j] = num[j]+maxgather[u];
                }else if(tu[u][j]+dis[u]==dis[j]){
                    num_of_luxian[j]+=num_of_luxian[u];
                    maxgather[j] = max(maxgather[j],maxgather[u]+num[j]);
                }
            }
        }
    }
}

int main(){
    fill(visited,visited+500,false);
    fill(dis,dis+500,INF);
    fill(tu[0],tu[0]+500*500,INF);
    fill(num_of_luxian,num_of_luxian+500,0);
    fill(maxgather,maxgather+500,0);
    cin>>n>>m>>c1>>c2;
    for(int i = 0;i<n;i++){
        cin>>num[i];
    }
    for(int i = 0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        tu[a][b] = c;
        tu[b][a] = c;
    }

    dijs();
    cout<<num_of_luxian[c2]<<" "<<maxgather[c2]<<endl;


    return 0;
}

发表于 2021-10-27 10:04:02 回复(0)

C/C++

ShawnLuooo

给一个Bellman Ford算法的版本

#include <cstdio>
(802)#include <vector>
#include <set>
(855)#include <climits>
#include <algorithm>

using namespace std;

const int maxv = 500;
const int INF = INT_MAX;

struct edge{
    int e_end, e_weight;
    edge(int a, int b): e_end(a), e_weight(b) {}
};

int N, M, S, D;
int v_weight[maxv], d[maxv];
int path_count[maxv]={};
int team[maxv]={};
vector<edge> graph[maxv];
set<int> pre[maxv];

void init();
void bellmanFord();

int main(){
    scanf("%d%d%d%d", &N, &M, &S, &D);
    for(int i=0; i<N; i++) scanf("%d", &v_weight[i]);
    while(M--){
        int c1, c2, l;
        scanf("%d%d%d", &c1, &c2, &l);
        graph[c1].push_back(edge(c2, l));
        graph[c2].push_back(edge(c1, l));
    }
    init();
    bellmanFord();
    printf("%d %d", path_count[D], team[D]);

    return 0;
}

void init(){
    fill(d, d+N, INF);
    d[S] = 0;
    path_count[S] = 1;
    team[S] = v_weight[S];
    return;
}

void bellmanFord(){
    for(int k=0; k<N-1; k++){
        //最多N-1次循环
        for(int i=0; i<N; i++){
            //每个顶点i
            if(d[i]==INF) continue; //重要
            int e = graph[i].size();
            for(int j=0; j<e; j++){
                //每条边i -> v
                int v = graph[i][j].e_end;
                int w = graph[i][j].e_weight;
                if(d[i]+w<d[v]){
                    //第一标准更优。找到更短路径
                    d[v] = d[i] + w;
                    team[v] = team[i] + v_weight[v];
                    path_count[v] = path_count[i];
                    pre[v].clear();
                    pre[v].insert(i);
                }
                else if(d[i]+w==d[v]){
                    //第一标准失效。找到长度相同的另一条路
                    //重新统计路径条数
                    pre[v].insert(i);
                    path_count[v] = 0;
                    for(set<int>::iterator it=pre[v].begin(); it!=pre[v].end(); it++){
                        path_count[v] += path_count[*it];
                    }
                    //第二标准更优
                    if(team[i]+v_weight[v]>team[v]){
                        team[v] = team[i] + v_weight[v];
                    }
                }
            }
        }
    }
    return;
}

发表于 2020-02-24 17:45:31 回复(0)

YwainY

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

#include <cstring>

using namespace std;

struct city{

int city_code;

int road_length;

vector<int> pre;

};

int city_num,road_num,city_start,city_end;

vector<city> city_node[510];

int length[510];

int flag[510]={0};

vector<int> pre[510];

const int INF=1000000000;

int djk(int start){

for(int k=0;k<city_num;k++) {

int min=INF;

int min_city;

for (int i = 0; i < city_node[start].size(); i++) {

if(length[city_node[start][i].city_code]==INF){

pre[city_node[start][i].city_code].push_back(start);

length[city_node[start][i].city_code] = city_node[start][i].road_length;

}

if (city_node[start][i].road_length < min&&flag[city_node[start][i].city_code]==0) {

min_city = city_node[start][i].city_code;

min = city_node[start][i].road_length;

}

if (min == INF) {

return 0;

}else{

flag[min_city]=1;

length[min_city]=min;

// for (int i = 0; i < city_node[start].size(); i++) {

// length[city_node[start][i].city_code] = city_node[start][i].road_length;

// if(flag[city_node[start][i].city_code]==0&&city_node[start][i].road_length < min){

// pre[city_node[start][i].city_code].push_back(start);

// }

for (int i = 0; i < city_node[min_city].size(); i++) {

if(city_node[min_city][i].city_code==start){

continue;

}

if(flag[city_node[min_city][i].city_code]==0&&min+city_node[min_city][i].road_length<length[city_node[min_city][i].city_code]){

// length[city_node[min_city][i].city_code]=min+city_node[min_city][i].road_length;

city tmp;

if(length[city_node[min_city][i].city_code]!=INF){

length[city_node[min_city][i].city_code]=min+city_node[min_city][i].road_length;

pre[city_node[min_city][i].city_code].clear();

pre[city_node[min_city][i].city_code].push_back(min_city);

for(int j=0;j<city_node[start].size();j++){

if(city_node[start][j].city_code==city_node[min_city][i].city_code){

city_node[start][j].road_length=min+city_node[min_city][i].road_length;

}

}else{

tmp.city_code=city_node[min_city][i].city_code;

tmp.road_length=min+city_node[min_city][i].road_length;

city_node[start].push_back(tmp);

pre[city_node[min_city][i].city_code].push_back(min_city);

length[city_node[min_city][i].city_code]=min+city_node[min_city][i].road_length;

// pre[city_node[start][i].city_code].push_back(start);

}

// length[city_node[min_city][i].city_code]=min+city_node[min_city][i].road_length;

}else{

// length[city_node[min_city][i].city_code]=min+city_node[min_city][i].road_length;

if(flag[city_node[min_city][i].city_code]==0&&min+city_node[min_city][i].road_length==length[city_node[min_city][i].city_code]){ //处理相等情况

int change=0;

for(int j=0;j<pre[city_node[min_city][i].city_code].size();j++){

if(pre[city_node[min_city][i].city_code][j]==min_city){

change=1;

}

if(change==0){

pre[city_node[min_city][i].city_code].push_back(min_city);

}

vector <int> road_record[510];

//int dg(int &short_num,int end,int start){

// for(int i=0;i<pre[end].size();i++){

// if(pre[end][i]==start){

// road_record[short_num].push_back(start);

// short_num++;

//

// continue;

// }else{

// road_record[short_num].push_back(pre[end][i]);

// dg(short_num,pre[end][i],start);

// }

//}

void dg(int &short_num,int &end){

if(end==city_start){

//road_record[short_num].push_back(start);

short_num++;

return;

}else{

for(int i=0;i<pre[end].size();i++){

//road_record[short_num].push_back(pre[end][i]);

//int o= pre[end][i];

//cout<<"-------------"<<pre[end][i]<<endl;

dg(short_num,pre[end][i]);

}

vector<int> team_num;

int sum_max=-INF;

struct md{

int code;

int jichen;

};

queue<md> kewu;

int kewu_sum=0;

int qiu_max(){

for(int i=0;i<pre[city_end].size();i++){

md tmp_md;

tmp_md.code=pre[city_end][i];

tmp_md.jichen=team_num[city_end]+team_num[tmp_md.code];

kewu.push(tmp_md);

}

kewu_sum+=team_num[city_end];

while(kewu.empty()!=1){

if(kewu.front().code==city_start){

if(sum_max<kewu.front().jichen){

sum_max=kewu.front().jichen;

}

kewu.pop();

continue;

}

for(int j=0;j<pre[kewu.front().code].size();j++){

md tmp_md;

tmp_md.code=pre[kewu.front().code][j];

tmp_md.jichen=kewu.front().jichen+team_num[tmp_md.code];

kewu.push(tmp_md);

}

kewu.pop();

}

return sum_max;

}

int main() {

int short_num=0;

scanf("%d %d %d %d",&city_num,&road_num,&city_start,&city_end);

int num_team;

for(int i=0;i<city_num;i++){

scanf("%d",&num_team);

team_num.push_back(num_team);

}

int c_a,c_b,len;

city temp_city;

for(int j=0;j<road_num;j++){

scanf("%d %d %d",&c_a,&c_b,&len);

temp_city.city_code=c_b;

temp_city.road_length=len;

city_node[c_a].push_back(temp_city);

temp_city.city_code=c_a;

city_node[c_b].push_back(temp_city);

}

if(city_start==city_end){

cout<<"1 "<<team_num[city_start]<<endl;

return 0;

}

fill(length,length+510,INF);

djk(city_start);

dg(short_num,city_end);

int max=-INF;

for(int i=0;i<short_num;i++){

int sum=0;

for(int j=0;j<road_record[i].size();j++){

sum+=team_num[road_record[i][j]];

}

if(sum>max){

max=sum;

}

max=qiu_max();

printf("%d %d\n",short_num,max);

}

发表于 2019-12-09 18:22:21 回复(0)

名字的响亮的

有人错在这个用例吗(牛客网只给了部分数据)？没找到原因。求指教。

编辑于 2019-07-28 21:00:52 回复(3)

MemoryC

最短路径问题

最初我使用经典的A*算法进行解题，奈何测试用例较大时递归超时且内存超限，后来改用迪杰克斯特拉算法（Dijkstra算法），终于通过。我把两个算法的代码都贴上来

1、Dijkstra算法（100%AC）

//MemoryC 20190508

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    private static int[]rescueNumbers;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);

        int N=scanner.nextInt();
        int M=scanner.nextInt();
        int C1=scanner.nextInt();
        int C2=scanner.nextInt();

        rescueNumbers=new int[N];
        List<Integer> cities=new ArrayList<>();

        for(int i=0;i<N;i++){
            rescueNumbers[i]=scanner.nextInt();
            cities.add(i);
        }

        for(int i=0;i<M;i++){
            Road.addRoad(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
        }

        List<Route> routes=findRoutes(cities,C1,C2);

        System.out.println(routes.size()+" "+routes.get(0).rescueNumber);
    }

    private static List<Route>findRoutes(List<Integer> cities, int from, int to){

        List<Route> routes=new ArrayList<>();
        if(from==to){
            Route route=new Route(0,rescueNumbers[from]);
//            route.rt="—>"+from;
            routes.add(route);
            return routes;
        }

        List<Road>roads=Road.getRoadsByCity(cities,from);

        int minLength=Integer.MAX_VALUE;
        int maxRescue=0;

        List<Integer> subCities = new ArrayList<>(cities);
        subCities.remove(Integer.valueOf(from));

        for(Road road:roads){
            int otherCity=road.city1^road.city2^from;

            List<Route>subRoutes=findRoutes(subCities,otherCity,to);

            if(subRoutes.isEmpty()){
                continue;
            }

            for(Route subRoute:subRoutes){
                subRoute.length+=road.length;

                if(subRoute.length<minLength){
                    minLength=subRoute.length;
                    routes.clear();
                }

                if(subRoute.length==minLength){
                    subRoute.rescueNumber+=rescueNumbers[from];
//                    subRoute.rt="—>"+from+subRoute.rt;
                    if(subRoute.rescueNumber>maxRescue){
                        maxRescue=subRoute.rescueNumber;
                        routes.add(0,subRoute);
                    }else {
                        routes.add(subRoute);
                    }
                }
            }
        }

        return routes;
    }

    static class Road{
        int city1;
        int city2;
        int length;
        private  static List<Road>roads=new ArrayList<>();

        static List<Road> getRoadsByCity(List<Integer>cities,int city){
            List<Road> roadList=new ArrayList<>();
            for(Road road:roads){
                if((cities.contains(road.city1)&&cities.contains(road.city2))&&(road.city1==city||road.city2==city)){
                    roadList.add(road);
                }
            }
            return roadList;
        }

        static void addRoad(int city1, int city2, int length) {
            Road road=new Road();
            road.city1 = city1;
            road.city2 = city2;
            road.length = length;
            roads.add(road);
        }
    }

    static class Route{
        int length;
        int rescueNumber;
//        String rt;

        Route(int length, int rescueNumber) {
            this.length = length;
            this.rescueNumber = rescueNumber;
        }
    }
}

2、A*算法（4个样例超时，其余正确）

//MemoryC 20190508

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main_Dijkstra {

    private static int[]rescueNumbers;
    static  Road[][] roads;

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);

        int N=scanner.nextInt();
        int M=scanner.nextInt();
        int C1=scanner.nextInt();
        int C2=scanner.nextInt();

        rescueNumbers=new int[N];
        roads=new Road[N][N];

        for(int i=0;i<N;i++){
            rescueNumbers[i]=scanner.nextInt();
        }


        List<Road> sureList=new ArrayList<>();
        List<Road> unSureList=new ArrayList<>();

        for(int i=0;i<M;i++){
            int c1=scanner.nextInt();
            int c2=scanner.nextInt();
            Road road=new Road(c1,c2,scanner.nextInt());
            roads[c1][c2]=road;
            roads[c2][c1]=road;

            if(c1==C1||c2==C1){
                unSureList.add(road);
            }
        }

        while (!unSureList.isEmpty()){
            int minLength=0x7fffffff;
            List<Road> minRoads=new ArrayList<>();
            for(Road r:unSureList){
                if(r.length<minLength){
                    minRoads.clear();
                    minRoads.add(r);
                    minLength=r.length;
                }else if(r.length==minLength){
                    minRoads.add(r);
                }
            }
            sureList.addAll(minRoads);
            unSureList.removeAll(minRoads);
            //更新U
            if(unSureList.isEmpty()||minRoads.contains(roads[C1][C2])){
                break;
            }else{
                for(Road ur:unSureList){
                    int tar=ur.city1^ur.city2^C1;
                    for(Road sr:minRoads){
                        int mid=sr.city1^sr.city2^C1;

                        if(mid==tar||roads[tar][mid]==null){
                            continue;
                        }

                        int twoLen=sr.length+roads[tar][mid].length;
                        if(twoLen<ur.length){
                            ur.length=twoLen;
                            ur.rescueNumber=sr.rescueNumber+roads[tar][mid].rescueNumber-rescueNumbers[mid];
                            ur.routeCount=1;

                        }else if(twoLen==ur.length){
                            ur.rescueNumber=Integer.max( ur.rescueNumber,sr.rescueNumber+roads[tar][mid].rescueNumber-rescueNumbers[mid]);
                            ur.routeCount++;

                        }
                    }
                }
            }
        }

        System.out.println(roads[C1][C2].routeCount+" "+roads[C1][C2].rescueNumber);
    }

    static class Road{
        int city1;
        int city2;
        int length;
        int routeCount=1;
        int rescueNumber;

        Road(int city1, int city2, int length) {
            this.city1 = city1;
            this.city2 = city2;
            this.length = length;
            rescueNumber=rescueNumbers[city1]+rescueNumbers[city2];
        }
    }
}

其实A*算法还是挺容易理解的，奈何超时

发表于 2019-05-08 14:36:14 回复(0)

C/C++

MniQ

#include <iostream>

using namespace std;

//1003 Emergency
//刷PAT以来第一个图算法，加深了理解
//初始值很重要，把dist[source]=0之后，并不设置visited[source]=1
//保证第一次会选中source点

#define inf 1e9
int main() {
    int n, m, c1, c2;
    int g[500][500] = {}, teams[500] = {};
    int dist[500] = {}, visited[500] = {};
    int cnt[500] = {}; //cnt[i]表示从c1到点i的最短路数量
    int gather[500] = {}; //gather[i]表示到达i点能收集到的救援队数量
    cin >> n >> m >> c1 >> c2;

    //输入救援队伍库存
    for (int i = 0; i<n; i++) {
        cin >> teams[i];
    }

    //初始化图
    fill(g[0], g[0] + 500 * 500, inf);

    //输入图
    for (int i = 0; i<m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = z;
        g[y][x] = z;
    }

    //初始化dist[] , visited[] , cnt[], gather[]
    for (int i = 0; i<n; i++) {
        dist[i] = g[c1][i];
    }
    dist[c1] = 0; //不这样写的话，本题默认的g[c1][c1]=inf，第一次循环取不到c1点，就不能从c1开始更新cnt[]与gather[]
    cnt[c1] = 1;
    gather[c1] = teams[c1];

    //小迪
    int k, min;
    for (int i = 0; i<n - 1; i++) {
        min = inf;
        for (int j = 0; j<n; j++) {
            if (!visited[j]) {
                if (dist[j] < min) {
                    min = dist[j];
                    k = j;
                }
            }
        }
        //已找到最小k
        visited[k] = 1;
        //更新dist
        for (int w = 0; w<n; w++) {
            if (!visited[w] && g[k][w] <inf) { //未访问过的k的邻接点w
                if (dist[k] + g[k][w]<dist[w]) {
                    dist[w] = dist[k] + g[k][w];
                    cnt[w] = cnt[k]; //从k点来w点的最短路数量是cnt[k]
                    gather[w] = gather[k] + teams[w]; //带来的兵与本地的兵
                }
                else if (dist[k] + g[k][w] == dist[w]) {
                    cnt[w] += cnt[k]; //路径长度相同时，路径数量叠加
                    if (gather[w]<gather[k] + teams[w]) {
                        gather[w] = gather[k] + teams[w]; //取最大可携队伍数
                    }
                }
            }//-end if
        }//end-for

    }
    //end-dijkstra

    cout << cnt[c2] << " " << gather[c2];

    return 0;
}

编辑于 2019-01-10 18:20:27 回复(0)

Emergency (25)

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题