最短絡特集【基礎編】(updating...)

hud1548 a strange lift  最短/bfs テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1548
标题:奇妙なエレベーターで、各階のボタンはi+k[i]階までしか上がらず、i-k[i]階まで降りることができません.n階を超えたり、1階を下回ったりすることはできません.最小ボタン数を聞く.入力を1つの0で終了します.
考え方:bfsは、出発点から1階に1回しかアクセスできず、アウトにならずに到着できるフロアにアクセスします.
まとめ:布吉島神馬の原因は、G++で渡すしかないので、何日も悩んでいました.
ACコード:

//AC
#include
#include
#include
#include
#include
using namespace std;
#define maxn 2000
#define INF INT_MAX
int n, a, b;
int arr[maxn];
bool inq[maxn];
int dis[maxn];

void bfs(int st){
   queue q;
   q.push(st);
   int x;
   dis[st] = 0;
   if(a < 1||a > n||b < 1||b > n) return;
   while(!q.empty()){
     x = q.front();
     q.pop();
     if(x < 1||x > n||x == b) break;
     if(x+arr[x] >= 1&&x+arr[x] <= n&&!inq[x+arr[x]]) { q.push(x+arr[x]); inq[x+arr[x]] = 1; dis[x+arr[x]] = dis[x] + 1; }
     if(x-arr[x] >= 1&&x-arr[x] <= n&&!inq[x-arr[x]]) { q.push(x-arr[x]); inq[x-arr[x]] = 1; dis[x-arr[x]] = dis[x] + 1; }
     //if(x+arr[x]>n&&x-arr[x]<1) break;
   }
}
int main(){
   while(~scanf("%d",&n) ,n){
    scanf("%d%d", &a, &b);
      for(int i = 1; i <= n; i++)
        scanf("%d",&arr[i]);
      memset(inq, 0, sizeof(inq));
      for(int i = 0; i <= maxn; i++){
        dis[i] = INF;
      }
      bfs(a);
      printf("%d
", (dis[b] == INF)?-1:dis[b]);
   }
}

hdu2544    
最短タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2544
題名:題名の通り最短であり,単源最短入門問題といえる.
構想:dijkstraですることができて、ここで私はspfaを使って、書く規則が規範的ではないことを知らないで、要するに構想はbellman-fordととても似ていて、Bellman-fordのキューの最適化に相当して、bfsを1回することにも相当して、具体的には現在のノードから出発して、すべてのノードにアクセスして、もし達することができるならば、また、アクセスされたノードから開始点までの値が現在のノードから開始点までの値に現在のノードからそのノードまでの値を加算すると、アクセスされたノードから開始点までの値が更新され、ノードがキューにない場合、エンキューされ、複雑度が最も悪いのはO(mn)である.
まとめ:waを書き終えてN+1回渡したが、最後にINFの値が設定されていないことに気づいた.Σ(っ°)Д °;)を小さくすると更新後の距離より小さくなる可能性があります.大きくします.例えばINT_MAXがまた溢れてきました...その後、ノード数Xの単一パスの最大距離を設定する もう少し大きくなると過ぎてしまいます~~T^T
MACコードは以下の通りである.

#include
#include
#include
#include
#include
using namespace std;
#define maxn 109
#define INF 1000011
int n, m, w[maxn][maxn];
void spfa()
{
  int d[maxn], k;
  bool inq[maxn];
  for(int i = 0; i <= n; i++) {d[i] = INF; inq[i] = false;}
  d[1] = 0;
  //inq[1] = true;
  queue q;
  q.push(1);
  while(!q.empty()){
     k = q.front(); q.pop();
     inq[k] = false;
     for(int j = 2; j <= n; j++){
       int t = d[k] + w[k][j];
       if(d[j] > t){
          d[j] = t;
          if(!inq[j]){
             q.push(j);
             inq[j] = true;
          }
       }
     }
  }
  printf("%d
",d[n]);
}

int main()
{
  while(scanf("%d%d", &n, &m)&&n&&m){
    for(int i = 0; i <= n; i++)
     for(int j = 0; j <= n; j++)
        w[i][j] = (i == j)?0:INF;

    for(int i = 0; i < m; i++){
       int a, b, c;
       scanf("%d%d%d", &a, &b, &c);
       w[a][b] = w[b][a] =c;
    }
    spfa();
  }
  return 0;
}

hdu 3790最短経路問題ベース最短★
考え方:基礎最短、経路を考えてから費用を考える
まとめ:WA原因、入力時にa,bの間に複数のパスが存在することを考慮していない
ACコード:
spfa版

//spfa 

#include
#include
#include
#include
#include
using namespace std;
#define maxn 2000
#define INF INT_MAX-100001
int n, m, a, b, d, p, s, t;
int w[maxn][maxn], cost[maxn][maxn];
struct node{
  int dis, cos;
};

void test(node* x){
  for(int i = 0; i <= n; i++)
  {
     cout< q;
  q.push(s);
  while(!q.empty()){
     k = q.front(); q.pop();
     inq[k] = false;
     for(int i = 0; i <= n; i++){
       if(i != k){
         int t1 = d[k].dis + w[k][i];  int t2 = d[k].cos + cost[k][i];
         if(t1 < d[i].dis){
           d[i].dis = t1;
           d[i].cos = t2;
           if(!inq[i]) { q.push(i); inq[i] = true; }
         }
         if(t1 == d[i].dis&&t1 != INF){
           if(t2 < d[i].cos) {
            d[i].cos = t2;
           }
           if(!inq[i]){ q.push(i); inq[i] = true; }
         }
       }
     }
  }
  //test(d);
  printf("%d %d
", d[t].dis, d[t].cos);

}
void init()
{
  for(int i = 0; i <= n; i++)
    for(int j = 0; j <= n; j++){
       w[i][j] = cost[i][j] = (i == j)?0:INF;
    }
}
int main()
{
  while(scanf("%d%d", &n, &m),n,m){
    init();
    for(int i = 0; i < m; i++){
      scanf("%d%d%d%d", &a, &b, &d, &p);
      if(d < w[a][b]){
      w[a][b] = w[b][a] = d;
      cost[a][b] = cost[b][a] = p;
      }
    }
    scanf("%d%d", &s, &t);

    spfa(s, t);
  }
  return 0;
}

dijkstra版

#include
#include
#include
#include
#include
#include
#include
#include
#define maxn 1024
#define INF 0x3fffffff
using namespace std;
int n, m;
int d[maxn];
struct node{
   int dis, cos;
};
node arr[maxn][maxn];

void test(int* c, int*d){
  for(int i = 1; i <= n; i++){
   cout< d[k] + arr[k][j].dis){
        d[j] = d[k] + arr[k][j].dis;
        cost[j] = cost[k] + arr[k][j].cos;
      }
      else if(d[j] < INF && d[j] == d[k] + arr[k][j].dis && cost[j] > cost[k] + arr[k][j].cos){
        cost[j] = cost[k] + arr[k][j].cos;
      }
    }
  }
//test(d, cost);
  printf("%d %d
", d[t], cost[t]);
}

int main(){
  while(scanf("%d%d", &n, &m) == 2 &&(n||m)){
    for(int i = 0; i <= n; i++){
      for(int j = 0; j <= n; j++)
      {
        arr[i][j].dis = arr[i][j].cos = (i == j)?0:INF;
      }
    }
    for(int i = 0; i < m; i++){
      int a, b, c, d;
      scanf("%d%d%d%d", &a, &b, &c, &d);
      if(c < arr[a][b].dis){
        arr[a][b].dis = arr[b][a].dis = c;
        arr[a][b].cos = arr[b][a].cos = d;
      }
    }
    int s, t;
    scanf("%d%d", &s, &t);
    dijkstra(s, t);
  }
  return 0;
}

hdu 2066一人旅 【多源多匯、基礎最短】
構想:隣接表存図.マルチソースマルチウェイのため、通常は0点で、この点からすべての起点までの距離は0で、それから裸の最短ルートになる「スーパー原点」を確立することを考慮します.
まとめ:なぜか自分のパソコンでinit()をした後、sはわけがわからずtと同じ値に変更されました...しかし、C++を无修正で渡したことがあります.
MACコードは以下の通りである.

//AC
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 1010
#define INF INT_MAX-1000
struct node{
   int v, wei;
};
vector gra[maxn];
int t, s, d;  int dis[maxn];

void init()
{
    int i;
    for(i = 0; i <= maxn; i++)
        gra[i].clear();
}

void input()
{
   for(int i = 0; i < t; i++){
       node re;
       int u, v, w;
       scanf("%d%d%d", &u, &v, &w);
       re.v = v; re.wei = w;
       gra[u].push_back(re);
       re.v = u;
       gra[v].push_back(re);
   }
   for(int i = 0; i < s; i++){
       node re; re.wei = 0;
       scanf("%d", &re.v);
       gra[0].push_back(re);
       int t = re.v; re.v = 0;
       gra[t].push_back(re);
   }
}

void output()
{
   int ans = INF;
   for(int i = 0; i < d; i++){
     int fina;
     scanf("%d", &fina);
     if(dis[fina] < ans) ans = dis[fina];
   }
   printf("%d
", ans);
}


void spfa()
{
   bool inq[maxn];  memset(inq, 0, sizeof(inq));
   for(int i = 0; i < maxn; i++)
     dis[i] = INF;

   queue q;
   q.push(0);
   inq[0] = true; dis[0] = 0;
   while(!q.empty()){
      int u = q.front(); q.pop();
      inq[u] = false;
      for(int i = 0; i < gra[u].size(); i++){
        int t = dis[u] + gra[u][i].wei;
        int v = gra[u][i].v;
        if(dis[v] > t){
          dis[v] = t;
          if(!inq[v]){
            q.push(v);
            inq[v] = true;
          }
        }
      }
   }
}

int main()
{
   while(scanf("%d%d%d", &t, &s, &d) != EOF){
     init();
     input();
     spfa();
     output();
   }
   return 0;
}

同じタイプの基礎問題は以下の通りです.
1869 ろくどぶんり Floyd最短回路