首页 > > 程序设计 > C/C++ >

分道扬镳

2018-06-18 04:20:13来源：未知阅读 ()

Description

编号为1…N 的N个城市之间以单向路连接，每一条道路有两个参数：路的长度和通过这条路需付的费用。

Bob和Alice生活在城市1，但是当Bob发现了Alice玩扑克时欺骗他之后，他决定与她翻脸，离开城市1前往城市N。Bob想尽快到达城市N，但是他的钱不多。

希望你帮助Bob找到一条从城市1到城市N的总费用不超过Bob的承受能力的最短路径。

Input

输入的第一行是3个整数 K, N, R ，其中：

K：表示Bob能承受的最大费用，0 ≤ K ≤ 10000

N：表示城市的总数，2 ≤ N ≤ 100

R：表示道路的条数，1 ≤ R ≤ 10000

接下来的R行，每行用S D L T（以空格隔开）表示一条道路：

S：表示道路的出发城市，1 ≤ S ≤ N

D：表示道路的目标城市，1 ≤ D ≤ N

L：表示道路的长度，1 ≤ L ≤ 100

T：表示通过这条道路需付的费用，0 ≤ T ≤ 100

Output

为每个测试用例输出一行结果：总费用小于或等于最大费用K的最短路径的长度。如果这样的路径不存在，则仅仅输出 -1 。

Sample Input

5 6 7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

Sample Output

Hint

测试数据的图中可能有重边、有自环。

这题有一定难度，但学完DFS和BFS就要能够AC它。它是一道典型的搜索题，而且需要强剪枝（去掉当前已知无效的搜索路径），以便加快搜索速度。

　　一看题目，发现很像PTA里的一道题目：<a href = "https://pta.patest.cn/pta/test/558/exam/4/question/9931">旅游规划</a>，但是解决思路不同，旅游规划那道题是用迪杰斯特拉算法的变形，这道题的思路是搜索所有城市1到城市N的可能路径，然后选一条费用不超过K的最短路径，有则输出最短路径长度，没有则输出-1。

伪代码：

 1 DFS（LGraph G， int i， int K）
 2 {
 3     if（i == N）//说明搜索到了N城市
 4     　　bestDist = currDist; //最短路径=当前路径
 5     else
 6     {
 7            循环每一个G中下标为i的顶点的邻接点
 8                 if(visited[adjvertex] == false && ck+adjvertex.cost<= K 
 9                 && currDist+adjvertex.dist<bestDist)
10                 { /*如果邻接点没有被访问，剪枝：当前费用ck+到邻接点费用小于等于K，当前距离+到邻接点的距离小于最短距离*/
11                          ck+=adjvertex.cost;
12                          currDist+=adjvertex.dist;
13                          DFS(G, adjvertex, K);
14                          ck-=adjvertex.cost;
15                          currDist-=adjvertex.dist;
16
17                 }
18      }
19     
20      return bestDist;
21 }

  1 //DFS 函数自己实现才有收获
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <stdbool.h>
  5 #include <string.h>
  6 
  7 #define MaxVertexNum 101    /* 最大顶点数设为101 */
  8 typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
  9 typedef struct{         /* 边的权值设为距离和花费 */
 10     int dist, cost;
 11 }WeightType;
 12   
 13 /* 边的定义 */
 14 typedef struct ENode *PtrToENode;
 15 struct ENode{
 16     Vertex V1, V2;      /* 有向边<V1, V2> */
 17     WeightType Weight;  /* 权重 */
 18 };
 19 typedef PtrToENode Edge;
 20   
 21 /* 邻接点的定义 */
 22 typedef struct AdjVNode *PtrToAdjVNode; 
 23 struct AdjVNode{
 24     Vertex AdjV;        /* 邻接点下标 */
 25     WeightType Weight;  /* 边权重 */
 26     PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
 27 };
 28   
 29 /* 顶点表头结点的定义 */
 30 typedef struct Vnode{
 31     PtrToAdjVNode FirstEdge;/* 边表头指针 */
 32 } AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
 33   
 34 /* 图结点的定义 */
 35 typedef struct GNode *PtrToGNode;
 36 struct GNode{  
 37     int Nv;     /* 顶点数 */
 38     int Ne;     /* 边数   */
 39     AdjList G;  /* 邻接表 */
 40 };
 41 typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
 42 
 43 LGraph BuildGraph();
 44 LGraph CreateGraph( int VertexNum );
 45 void InsertEdge( LGraph Graph, Edge E );
 46 int DFS(LGraph G, int n);
 47 
 48 bool visited[MaxVertexNum];
 49 int K;
 50 int ck;            //当前花费
 51 int bestDist;    //最好的路程
 52 int currDist;    //当前的路程
 53 
 54 int main()
 55 {
 56     int result;
 57     scanf("%d",&K);
 58     LGraph G = BuildGraph();
 59     memset(visited, false, sizeof(visited));
 60     ck = currDist = 0;
 61     visited[1] = true;
 62     bestDist = 0xffff;
 63     result = DFS(G, 1);
 64     if (bestDist == 0xffff) //说明没有符合的路径，返回-1
 65         result = -1;
 66     printf("%d\n",result);
 67     getchar();getchar();
 68     return 0;
 69 }
 70 
 71 LGraph CreateGraph( int VertexNum )
 72 { /* 初始化一个有VertexNum个顶点但没有边的图 */
 73     Vertex V;
 74     LGraph Graph;
 75       
 76     Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
 77     Graph->Nv = VertexNum;
 78     Graph->Ne = 0;
 79     /* 初始化邻接表头指针 */
 80     /* 注意：这里默认顶点编号从1开始，到(Graph->Nv) */
 81        for (V=1; V<=Graph->Nv; V++)
 82         Graph->G[V].FirstEdge = NULL;
 83               
 84     return Graph; 
 85 }
 86          
 87 void InsertEdge( LGraph Graph, Edge E )
 88 {
 89     PtrToAdjVNode NewNode;
 90       
 91     /* 插入边 <V1, V2> */
 92     /* 为V2建立新的邻接点 */
 93     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 94     NewNode->AdjV = E->V2;
 95     NewNode->Weight = E->Weight;
 96     /* 将V2插入V1的表头 */
 97     NewNode->Next = Graph->G[E->V1].FirstEdge;
 98     Graph->G[E->V1].FirstEdge = NewNode;
 99 }
100   
101 LGraph BuildGraph()
102 {
103     LGraph Graph;
104     Edge E;
105     Vertex V;
106     int Nv, i;
107       
108     scanf("%d", &Nv);   /* 读入顶点个数 */
109     Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
110       
111     scanf("%d", &(Graph->Ne));   /* 读入边数 */
112     if ( Graph->Ne != 0 ) { /* 如果有边 */ 
113         E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
114         /* 读入边，格式为"起点 终点 权重"，插入邻接表 */
115         for (i=0; i<Graph->Ne; i++) {
116             scanf("%d %d %d %d", &E->V1, &E->V2, &E->Weight.dist, &E->Weight.cost); 
117             InsertEdge( Graph, E );
118         }
119     } 
120     return Graph;
121 }