1131. Subway Map (30)

开始用dij求最短路径，结果超时，最后用dfs回溯剪枝，ac了

#include<iostream>
#include<vector>
#include<cstdlib>
#include<set>
#include<cstring>
#pragma warning(disable:4996)
using namespace std;
struct ArcNode {
    int line;
    int data;
    ArcNode *next;

};
struct VNode {
    ArcNode *first,*last;
    VNode() { first = last = NULL; }
};
struct renode {
    int be, en;
    int line;
    renode() = default;
    renode(int b, int e, int l) { be = b;en = e;line = l; }
};
struct resault {
    int length;
    vector<renode> all;
    resault() { length = 0;all.resize(0); }
    bool operator<(const resault b)const {
        return length < b.length ||
            (length == b.length && all.size() < b.all.size());
    }
};
set<int> all;
VNode vex[10000];
vector<int> line;
int visited[10000] = {};
//void dij(int beg, int end)
//{
//  memset(visited, 0, sizeof(visited));
//  visited[beg] = 1;
//  resault D[10000];
//  resault T[10000];
//  ArcNode *p = vex[beg].first;
//  while (p != NULL)
//  {
//      T[p->data].length++;
//      T[p->data].all.push_back(renode(beg, p->data, p->line));
//      p = p->next;
//  }
//  while (!visited[end])
//  {
//      resault m;
//      int v=0;
//      m.length = 99999;
//      for (auto t:all)
//          if (!visited[t] && T[t].length!=0 && T[t] < m) { m = T[t];v = t; }
//      D[v] = m;
//      visited[v] = 1;
//      p = vex[v].first;
//      while (p != NULL)
//      {
//          if (!visited[p->data])
//          {
//              int xxx = D[v].all.size();
//              if (D[v].all.back().line != p->line)  xxx++;
//              if (T[p->data].length == 0 || xxx<T[p->data].all.size()||T[p->data].length>D[v].length+1)
//              {
//                  resault temp = D[v];
//                  if (temp.all.back().line == p->line)
//                      temp.all.back().en = p->data;
//                  else
//                      temp.all.push_back(renode(temp.all.back().en, p->data, p->line));
//                  temp.length++;
//                  if (temp < T[p->data] || T[p->data].length == 0)
//                      T[p->data] = temp;
//              }
//          }
//          p = p->next;
//      }
//  }
//  printf("%dn", D[end].length);
//  for (auto x : D[end].all)
//  {
//      printf("Take Line#%d from %04d to %04d.n", x.line, x.be, x.en);
//  }
//}
resault temp;
resault re;
void dfs(int beg, int end)
{
    if (beg == end)
    {
        if (temp < re) re = temp;
    }
    if (re < temp) return;
    ArcNode *p = vex[beg].first;
    while (p != NULL)
    {
        if (!visited[p->data])
        {
            resault ttt = temp;
            temp.length++;
            if (temp.all.back().line != p->line)
                temp.all.push_back(renode(beg, p->data, p->line));
            else temp.all.back().en = p->data;
            visited[p->data] = 1;
            dfs(p->data, end);
            visited[p->data] = 0;
            temp = ttt;
        }
        p = p->next;
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    for (int i = 1;i <= N;i++)
    {
        int a, b;
        int K;
        scanf("%d", &K);
        scanf("%d", &a);
        //all.insert(a);
        for (int t = 1;t < K;t++)
        {
            scanf("%d", &b);
        //  all.insert(b);
            ArcNode *x = (ArcNode*)malloc(sizeof(ArcNode));
            ArcNode *y = (ArcNode*)malloc(sizeof(ArcNode));
            y->line=x->line = i;
            y->next=x->next = NULL;
            x->data = a;
            y->data = b;
            if (vex[a].first == NULL) vex[a].first = vex[a].last = y;
            else {
                vex[a].last->next = y;
                vex[a].last = y;
            }
            if (vex[b].first == NULL) vex[b].first = vex[b].last = x;
            else {
                vex[b].last->next = x;
                vex[b].last =x;
            }
            a = b;
        }
    }
    scanf("%d", &N);
    while (N--)
    {
        memset(visited, 0, sizeof(visited));
        int a, b;
        scanf("%d %d", &a, &b);
        visited[a] = 1;
        temp.length = 0;
        temp.all.assign(1,renode(a, a, 105));
        re.length = 99999;
        dfs(a, b);
        printf("%dn", re.length);
        for (auto x : re.all)
        {
            if(x.be!=x.en)
            printf("Take Line#%d from %04d to %04d.n", x.line, x.be, x.en);
        }
    }
}

最后

以上就是典雅书包为你收集整理的1131. Subway Map (30)的全部内容，希望文章能够帮你解决1131. Subway Map (30)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。