一本通T1261

SFxuks · 2020-03-01 19:35:27 · 个人记录

T1261

看上去像dp的最短路

保存路径用类似于静态链表的操作。

#include <bits/stdc++.h>
using namespace std;

int a[1001][1001];
int f[1001][1001];
int dis[1001];//dis记录第一个点到第i个点的长度
int pre[1001];//pre[i]表示到达i的前一个点
int vis[1001];//vis记录某个点是否被访问过

void print(int x)//递归输出路径
{
  if(x == 1)
  {
    printf("1 ");
    return;
  }
  print(pre[x]);
  printf("%d ", x);
}

int main()
{
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      scanf("%d", &a[i][j]), a[i][j] = a[i][j] == 0? 1e9:a[i][j], dis[j] = i == 1? a[i][j]:1e9;
  dis[1] = 0;
  for(int i = 1; i <= n; i++)
  {
    int Min = 1e9, p;
    for(int j = 1; j <= n; j++)//找出当前未访问过的可到达的最近的点
    {
      if(!vis[j] && dis[j] < Min) Min = dis[j], p = j;
    }
    vis[p] = 1;
    for(int j = 1; j <= n; j++)//类似dp的方法更新最短路径
      if(dis[p] + a[p][j] < dis[j]) dis[j] = dis[p] + a[p][j], pre[j] = p;//p为到达j的前一个点
  }
  printf("minlong=%d\n", dis[n]);
  print(n);
  return 0;
}