# L2-001. 紧急救援

```4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
```

```2 60
0 1 3
```

``````#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int INF =505;

struct node
{
int to,w,next;
};
node edge[INF * INF];
int pointW[INF];
int n,m,st,end;
/*

/*
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

2 60
0 1 3
*/
int Outpath(int k);		//输出路径

int path[INF];			//用类似链表的形式存路径

int main()
{
path[st]  = -1;
scanf("%d %d %d %d",&n,&m,&st,&end);
for(int i = 0; i < n; i++)
scanf("%d",&pointW[i]);				//用来存点权

//用链式前向星来存图---------------------------

for(int i =1; i <= 2*m; i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);

edge[i].to = b, edge[i].w =c, edge[i].next = head[a];
i++;
edge[i].to =a, edge[i].w =c, edge[i].next = head[b] ;
}

//分别用来存边权和，每个点的标记情况，和点权和
int dis[INF], book[INF],ans[INF];

//初始化--------------------------------
fill(dis,dis + INF,9999999);
dis[st] = 0;
fill(book,book + INF, 0);
book[st] = 1;
fill(book, book + INF, 0);
ans[st] = pointW[st];
queue <int> que;
que.push(st);

while(!que.empty())
{
int now = que.front();
book[now] = 0;
que.pop();

for(int k = head[now]; k != -1; k =edge[k].next)
{
//约束条件一，寻找边权和最大的情况
if(dis[edge[k].to] > dis[now] + edge[k].w)
{
dis[edge[k].to] = dis[now] + edge[k].w;
ans[edge[k].to] = pointW[edge[k].to] + ans[now];
path[edge[k].to] = now;
if(book[edge[k].to] == 0)
{
book[edge[k].to] = 1;
que.push(edge[k].to);
}
}
//约束条件二，在存在多个边权和相等的情况下求点权和最大
else if(dis[edge[k].to] == dis[now] + edge[k].w)
{
if(ans[edge[k].to] < pointW[edge[k].to] +ans[now] )
{
ans[edge[k].to] = pointW[edge[k].to] + ans[now];
path[edge[k].to] = now;
}
}
}

}
printf("%d %d\n",dis[end],ans[end]);

int k = end;

Outpath( k);

printf("%d\n",k);

return 0;
}
int Outpath(int k)
{
if(path[k] == -1)
return k;
else
{
printf("%d ",Outpath(path[k]));
return k;
}
}

``````