# Demo entry 6334029

Project2

Submitted by Ken on Dec 05, 2016 at 02:26
Language: C++. Code size: 5.6 kB.

```#include<stdio.h>
#include<stdlib.h>
#include<vector>

#define MaxStation 501
#define Max 1<<30//定义最大值
typedef int Vertex;

//因为结点最多可能到500，所以用链表来表示
int cost;
};//用来存放和Station[i]相邻的结点的结构

typedef struct Vnode{
int Dis;
int bike;
int isFind;
int Path;
std::vector<int> paths;//用来存放所有的最短路径的上一个结点
} Station[MaxStation];//存放所有的Station的各种数据

typedef struct GNode *PtrToGNode;//图的结构
struct GNode{
int Nv;
int Ne;
int wrongStation;
int capacity;
std::vector<int> finalPath;//存放最终路径
std::vector<int> Path;
int send;
int back;
Station stationG;
};
typedef PtrToGNode LGraph;

//因为最大结点数较大，故选用队列来记录数据
typedef struct Queue * queue;//队列的结构
struct Queue{
int VNode;
queue next;
};

typedef struct Q *q;//存放队列的头尾
struct Q{
queue tail;
};

void Push(int V, q Q){//Push函数，将数据推入队列中
queue tmp;
tmp = (queue)malloc(sizeof(struct Queue));
tmp->VNode = V;
tmp->next = NULL;
Q->tail->next = tmp;
Q->tail = tmp;
}

int Pop(q Q){//Pop函数，从队列中弹出数据
int V;
queue tmp;
if (!tmp)
return -1;
if (tmp == Q->tail)

V = tmp->VNode;

free(tmp);
return V;
}

//按照ppt上的来的算法，因为这是一个无向图，所以实际上采用的是类似negativeWeight的算法。
void Dijkstra(LGraph Graph);

//初始化图
LGraph Init();

//深度优先，从后往前遍历全部最短路径
void DFS(LGraph Graph, Vertex V, int send, int back);

int main(){
LGraph Graph = Init();//初始化图
int WS,V;//方便比较大小的几个辅助变量
int sendin = 0, sendback = 0;//存放最终输出

//找到最短路径
Dijkstra(Graph);
//借助paths，从WS开始往0查找，比较最佳路径，将最佳路径写入Path
WS = Graph->wrongStation;
DFS(Graph, WS,0,0);

//输出
printf("%d ", Graph->send);
printf("0");
for (int i = Graph->finalPath.size() - 1; i >= 0; i--){
printf("->%d", Graph->finalPath[i]);
}

printf(" %d", Graph->back);

}

LGraph Init(){//读入图的初始化函数
LGraph Graph;
int i,v1,v2,cost;
Graph = new GNode;
Graph->send  = Max;
Graph->back = Max;
//初始化
Graph->stationG[0].Dis = 0;
Graph->stationG[0].Path = 0;
Graph->stationG[0].FirstEdge->Next = NULL;
Graph->stationG[0].bike = 5;
Graph->stationG[0].isFind = 0;

//读入容量、结点数、错误结点值、边数
scanf("%d%d%d%d", &Graph->capacity, &Graph->Nv, &Graph->wrongStation, &Graph->Ne);

//printf("请输入自行车数\n");
for (i = 1; i <= Graph->Nv; i++){
scanf("%d", &Graph->stationG[i].bike);
Graph->stationG[i].FirstEdge->Next = NULL;
Graph->stationG[i].isFind = 0;
Graph->stationG[i].Dis = Max;
}//初始化

for (i = 0; i < Graph->Ne; i++){
//printf("请输入边\n");
scanf("%d%d%d", &v1, &v2, &cost);

tmpN->cost = cost;

tmpN->cost = cost;

}
return Graph;
}

void Dijkstra(LGraph Graph){
q Q = (q)malloc(sizeof(struct Q));
Vertex V, W, WS = Graph->wrongStation;
int tmpDis;
//初始化存放队列的结构

Push(0, Q);
while ((V = Pop(Q)) >= 0){
tmpW = Graph->stationG[V].FirstEdge->Next;

while (tmpW){
tmpDis = Graph->stationG[V].Dis + tmpW->cost;
if ( tmpDis < Graph->stationG[W].Dis){//如果找到更短的路径
Graph->stationG[W].Dis = tmpDis;
Graph->stationG[W].Path = V;
if (Graph->stationG[W].paths.size())
Graph->stationG[W].paths.clear();//清空vector
Graph->stationG[W].paths.push_back(V);//将数据存放入vector
Push(W, Q);
}
else if (tmpDis == Graph->stationG[W].Dis){//如果找到同样长度的路径
Graph->stationG[W].paths.push_back(V);//将新的路径（上一个结点）也存放到vector中
Push(W, Q);
}
tmpW = tmpW->Next;
}
}
}

void DFS(LGraph Graph, Vertex V, int send, int back){
int bestNum = Graph->capacity / 2;

if (V != 0 )//如果不是起始点，要继续遍历，直到起始点跳出递归
{
Graph->stationG[V].isFind = 1;//记录下已经过了这个结点
Graph->Path.push_back(V);//将该结点添加进vector中
if (Graph->stationG[V].bike <= bestNum)//如果结点中bike数比均值小，说明还需要送来车辆，增加send数
{
send = send + bestNum - Graph->stationG[V].bike;
}
else
{
back = back + Graph->stationG[V].bike - bestNum;//如果bike数大于均值，因为现在是从后往前遍历，所以可以削减send数
if (send > 0)//如果之前需要send过来车，可以从过剩结点运过去，send和back值都减少
{
if (back>send)//back数比较大，还需要back回起始点一些
{
back -= send;
send = 0;
}
else//send数比较大，还需要继续send
{
send -= back;
back = 0;
}
}
}

for (auto &tmp: Graph->stationG[V].paths)//对所有经过V的路径进行DFS搜索
{
DFS(Graph, tmp, send, back);
}
Graph->Path.pop_back();//结束一次递归后将tmp路径中原来的自己的值弹出
}
else if (V == 0)//如果到了起始点，结束递归
{
if (send < Graph->send){//send优先，如果现在的tmp路径比最终路径send值更小，改变最终路径
Graph->finalPath.clear();
Graph->finalPath = Graph->Path;
Graph->send = send;
Graph->back = back;
}
else if (send == Graph->send && back < Graph->back)//如果send值相同，比较back值
{
Graph->finalPath.clear();
Graph->finalPath = Graph->Path;
Graph->send = send;
Graph->back = back;
}
}
}
```

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.