首页 > 试题广场 >

Emergency (25)

[编程题]Emergency (25)
  • 热度指数:5159 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

输入描述:
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (<= 500) - the number of cities (and the cities are numbered from 0 to N-1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively.  The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city.  Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively.  
It is guaranteed that there exists at least one path from C1 to C2.


输出描述:
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
示例1

输入

5 6 0 2<br/>1 2 1 5 3<br/>0 1 1<br/>0 2 2<br/>0 3 1<br/>1 2 1<br/>2 4 1<br/>3 4 1

输出

2 4
第一次做图的题,写了两个上午啊。思路:用dijkstra+dfs
很奇怪,牛客通过率是90%,最后提示的是内存超限。但是在PAT网站可以完全通过
不过,如果要在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)
#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)
我真是服了,这里是正确的,但是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)
/*因为初学,被这道题目卡了一会,也好好研究了一下图论里的常用算法。
把自己的代码做了比较详细的注释,贴出来,很多不足的地方,还望大家批评指正。
基本的思路就是从终点的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)
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版。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)
//过了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)
没有用高大上的算法,直接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)
为啥在PTA上就有三个样例通不过
在牛客上就通过了
发表于 2019-11-13 10:40:59 回复(0)
#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)
用迪杰斯特拉算法即可。《算法笔记》上这个算法有三种扩展:增加边权,点权和计算几条最短路径。这个题是点权和计算几条最短路径两者的结合。
#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)
给一个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)
#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)
最短路径问题
最初我使用经典的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)
#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)
#include<stdio.h>
voidflyd(inta[][500],intb[][600],intn,intstart,intdest)
{
/*printf("\n\n");
for(int u=0;u<n;u++)
{
for(int v=0;v<n;v++)
{
printf("%d ",a[u][v]);
}
printf("\n");
}
printf("\n\n");*/
inty=a[start][dest];
for(intt=0;t<n;t++)
{
for(inti=0;i<n;i++)
{
for(intj=0;j<n;j++)
{
if(b[i][t]>=0&&b[t][j]>=0&&t!=j&&t!=i&&b[i][t]+b[t][j]<b[i][j])
{
b[i][j]=b[i][t]+b[t][j];
a[i][j]=a[i][t]+a[t][j];
a[j][i]=a[i][t]+a[t][j];
}elseif(b[i][t]>=0&&b[t][j]>=0&&t!=j&&t!=i&&b[i][t]+b[t][j]==b[i][j])
{
if(a[i][t]>0)
{
b[i][j]=b[i][t]+b[t][j];
a[i][j]=a[i][t]+a[t][j];
a[j][i]=a[i][t]+a[t][j];
}
}
}
}
/* printf("\n\n");
for(int u=0;u<n;u++)
{
for(int v=0;v<n;v++)
{
printf("%d ",a[u][v]);
}
printf("\n");
}
printf("\n\n");*/
}
printf("%d %d\n",b[start][dest],(a[start][dest]+y)/2);
}
intmain()
{
intstart,dest;
intn,m;
while(scanf("%d %d %d %d",&n,&m,&start,&dest)!=EOF)
{
intrescue[500][500];
for(inti=0;i<n;i++)
for(intj=0;j<n;j++)
{
rescue[i][j]=0;
}
intte;
for(inti=0;i<n;i++)
{
scanf("%d",&te);
for(intj=0;j<n;j++)
{
rescue[j][i]+=te;
rescue[i][j]=rescue[j][i];
}
}
intdis[600][600];
for(inti=0;i<n;i++)
for(intj=0;j<n;j++)
{
if(i!=j)
dis[i][j]=-1;
else
dis[i][j]=0;
}
for(inti=0;i<m;i++)
{
inttempa,tempb,tempc;
scanf("%d %d %d",&tempa,&tempb,&tempc);
dis[tempa][tempb]=dis[tempb][tempa]=tempc;
}
flyd(rescue,dis,n,start,dest);
}
return0;
}



这个测试案例怎么感觉是错的,2和0之间最短路径为1?????我手画也不是啊,有没有人知道测试是从哪里走的才能路径为1
编辑于 2018-12-04 23:02:29 回复(1)