題意：
中文題目大家應該都看得懂。
思路：
用dijkstra算法尋找最短路。
dijskstra算法的精髓是：一條兩頂點間的最短路徑包含路徑上其他的最短路徑。
舉個例子：有這麼一條1到6的最短路徑 1 -> 2 -> 4 -> 6 那麼從1到4的最短路則為 1-> 2 -> 4
證明：反證法，假設不是最短路，那麼必能找到一條比這個更短的路徑，而如果是這樣的話，原命題1到6的最短路徑就不成立了，由此得證。
基本思想：貪心
操作：
設定一個頂點集合S，從源點到S中頂點的最短路徑權值已經确定，通過反複從V-S中選取具有最短路徑估計的頂點u，将u加入S中，并松弛所有u的出邊，求得最短路徑
也可以用floyd，暴力的對每個點進行可能的松弛。
int dis[][];
void floyd(int n){ // n is the number of node
for(int k = ;k <= n;k++){
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
if(dis[i][j] > dis[i][k]+dis[k][j])
dis[i][j] = dis[i][k]+dis[k][j];
}
}
}
}
AC代碼：
dijkstra:
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
struct edge{
int y;
int v;
};
vector<edge> v[];
int dis[];
bool vis[];
void dijkstra(int N){
int n = ;
for(int i = ;i < v[].size();i++){
dis[v[][i].y] = v[][i].v;
}
int temp = ;
int pos;
for(int i = ;i <= N;i++){
if(vis[i] == false && dis[i] < temp)
temp = dis[i],pos = i;
}
vis[] = true;
while(n != N){
for(int i = ;i < v[pos].size();i++){
if(v[pos][i].v + dis[pos] < dis[v[pos][i].y]){
dis[v[pos][i].y] = v[pos][i].v + dis[pos];
}
}
vis[pos] = true;
temp = ;
for(int i = ;i <= N;i++){
if(vis[i] == false && dis[i] < temp)
temp = dis[i],pos = i;
}
n++;
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m),m){
memset(vis,false,sizeof(vis));
memset(dis,,sizeof(dis));//注意初始化為最大值
int x,temp2;
edge temp;
for(int i = ;i <= m;i++){
scanf("%d%d%d",&x,&temp.y,&temp.v);
v[x].push_back(temp);
temp2 = x;
x = temp.y;
temp.y = temp2;
v[x].push_back(temp);
}
dijkstra(n);
printf("%d\n",dis[n]);
for(int i = ;i < ;i++){//注意清空
v[i].clear();
}
}
return ;
}
floyd
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
int dis[][];
void floyd(int n){
for(int k = ;k <= n;k++){
for(int i = ;i <= n;i++){
for(int j = ;j <= n;j++){
if(dis[i][j] > dis[i][k]+dis[k][j])
dis[i][j] = dis[i][k]+dis[k][j];
}
}
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m),m){
memset(dis,,sizeof(dis));
int x,y,z;
for(int i = ;i <= m;i++){
scanf("%d%d%d",&x,&y,&z);
dis[x][y] = z;
dis[y][x] = z;
}
for(int i = ;i <= n;i++){//沒必要
dis[i][i] = ;
}
floyd(n);
printf("%d\n",dis[][n]);
}
return ;
}
也可以用優先隊列優化dijkstra：
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
struct edge{
int y;
int v;
bool operator < (const edge &b)const {
return v > b.v;
}
};
vector<edge> v[];
int dis[];
bool vis[];//是否已得到最短路
//bool vi[110];//是否以此點松馳過
void dijkstra(){
priority_queue<edge> q;
edge temp;
for(int i = ;i < v[].size();i++){
dis[v[][i].y] = v[][i].v;
temp.y = v[][i].y;
temp.v = v[][i].v;
q.push(temp);
}
vis[] = true;
int pos = q.top().y;
while(!q.empty()){
for(int i = ;vis[pos] == false && i < v[pos].size();i++){
if(v[pos][i].v + dis[pos] < dis[v[pos][i].y]){
dis[v[pos][i].y] = v[pos][i].v + dis[pos];
temp.y = v[pos][i].y;
temp.v = dis[v[pos][i].y];
q.push(temp);
}
}
vis[pos] = true;
q.pop(); // 注意：這行和下一行不能調換，否則可能遇到最後一個元素需要松弛而沒有松弛就跳出循環的悲劇。
pos = q.top().y;
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m),m){
memset(vis,false,sizeof(vis));
memset(dis,,sizeof(dis));//注意初始化為最大值
int x,temp2;
edge temp;
for(int i = ;i <= m;i++){
scanf("%d%d%d",&x,&temp.y,&temp.v);
v[x].push_back(temp);
temp2 = x;
x = temp.y;
temp.y = temp2;
v[x].push_back(temp);
}
dijkstra();
printf("%d\n",dis[n]);
for(int i = ;i < ;i++){//注意清空
v[i].clear();
}
}
return ;
}
AC代碼：（最終版本）
#include <iostream>
#include <cstdio>
#include <string.h>
#include <queue>
typedef long long int lli;
using namespace std;
const int NODE = ;
const int EDGE = ;
lli dis[NODE];
bool vis[NODE];// 是否已經松弛過
int head[NODE];//memset(head,-1,sizeof(head));
int cnte;//多樣例時注意清零
struct edge{
int to;
int v;
int next;
bool operator < (const edge &b)const {
return v > b.v;
}
}edg[*EDGE];
void addedge(int x,int y,int v){
edg[++cnte].to = y;
edg[cnte].v = v;
edg[cnte].next = head[x];
head[x] = cnte;
}
void dijkstra(int start){
priority_queue<edge> q;
int now = head[start];
while(now != -){
dis[edg[now].to] = edg[now].v;
q.push(edg[now]);
now = edg[now].next;
}
vis[start] = true;
dis[start] = ;
int pos;
while(!q.empty()){
pos = q.top().to;
now = head[pos];
while(vis[pos] == false && now != -){
if(edg[now].v + dis[pos] < dis[edg[now].to]){
dis[edg[now].to] = edg[now].v + dis[pos];
edge temp;
temp.to = edg[now].to;
temp.v = dis[edg[now].to];
q.push(temp);
}
now = edg[now].next;
}
vis[pos] = true;
q.pop();
}
}
int main()
{
int n,m;
int x,y,z;
while(scanf("%d%d",&n,&m),m){
if(n == ){
printf("0\n");
}
cnte = ;
memset(vis,false,sizeof(vis));
memset(head,-,sizeof(head));
memset(dis,,sizeof(dis));//注意初始化為最大值
for(int i = ;i <= m;i++){
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
dijkstra();
printf("%I64d\n",dis[n]);
}
return ;
}
![2017年團體程式設計天梯賽-決賽小結[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)