최 단 로 테마

HDU 2544 최 단 로http://acm.hdu.edu.cn/showproblem.php?pid=2544
제목: 1 부터 n 까지 의 최 단 시간 을 계산한다.
최 단 로 템 플 릿 문제...
 
Source Code：
（Dijkstra）：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int inf=0x3f3f3f3f;
const int nv=102;
int map[nv][nv];
int dis[nv];
bool s[nv];
int n,m;

int dijkstra(int src,int n){
    int i,j,u,tmp;
    for(int i=1;i<=n;i++){
        dis[i]=map[src][i];
        s[i]=false;
    }
    s[src]=true;
    dis[src]=0;
    for(i=1;i<n;i++){
        tmp=inf;
        for(j=1;j<=n;j++){
            if(!s[j]&&dis[j]<tmp){
                tmp=dis[j];
                u=j;
            }
        }
        s[u]=true;
        for(j=1;j<=n;j++){
            if(!s[j]&&map[u][j]+dis[u]<dis[j])
                dis[j]=map[u][j]+dis[u];
        }
    }
    return dis[n];
}

int main()
{
    while(~scanf("%d %d",&n,&m),n||m){
       memset(map,inf,sizeof(map));
       while(m--){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            if(map[u][v]>w) map[u][v]=map[v][u]=w;
       }
       printf("%d
",dijkstra(1,n));
    }
    return 0;
}

 
（Bellman Ford）：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int inf=0x3f3f3f3f;
const int nv=105;
struct Edge{
    int u,v,w;
}gra[nv*nv];
int dis[nv];

void BellmanFord(int n,int m){
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    for(int i=1;i<n;i++){
        for(int j=1;j<=m;j++){
            if(dis[gra[j].u]+gra[j].w<dis[gra[j].v]) dis[gra[j].v]=dis[gra[j].u]+gra[j].w;
            if(dis[gra[j].v]+gra[j].w<dis[gra[j].u]) dis[gra[j].u]=dis[gra[j].v]+gra[j].w;
        }
    }
}

int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m),n+m){
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            gra[i].u=u,gra[i].v=v,gra[i].w=w;
        }
        BellmanFord(n,m);
        printf("%d
",dis[n]);
    }
    return 0;
}

（spfa）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

const int maxn=105;
const int INF=0x3f3f3f3f;

int n,m;
int map[maxn][maxn],dis[maxn];
bool mark[maxn];

int Spfa(int src,int des){
    for(int i=0;i<=n;i++){
        mark[i]=false;
        dis[i]=INF;
    }
    queue<int>Q;
    mark[src]=true;
    dis[src]=0;
    Q.push(src);
    while(!Q.empty()){
        int first=Q.front();
        Q.pop();
        mark[first]=false;
        for(int i=1;i<=n;i++){
            if(dis[first]+map[first][i]<dis[i]){
                if(!mark[i]){
                    Q.push(i);
                    mark[i]=true;
                }
                dis[i]=dis[first]+map[first][i];
            }
        }
    }
    return dis[des];
}

int main()
{

    while(scanf("%d %d",&n,&m),n+m){
        int a,b,c;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)
                map[i][j]=INF;
        }
        while(m--){
            scanf("%d %d %d",&a,&b,&c);
            if(map[a][b]>c) map[a][b]=map[b][a]=c;
        }
        printf("%d
",Spfa(1,n));
    }
    return 0;
}

 
 
 
 
HDU 1548 A strange lift  http://acm.hdu.edu.cn/showproblem.php?pid=1548
제목: N 층 건물 은 층 마다 버튼 이 하나 있 고 위 나 아래 X 층 (물론 지하 로 달 려 가 거나 층 수 를 초과 할 수 없다) 이 있 습 니 다. A 층 에서 B 층 까지 최소 몇 번 의 버튼 을 누 르 라 고 물 었 습 니 다.
문제 풀이: 종이 에 그 려 보면 단원 최 단 로 라 고 생각 하기 쉽다.데이터 규모 가 작 기 때문에 BFS 를 사용 해도 됩 니 다.
 
Source Code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=205;
int Map[maxn][maxn],dis[maxn];
bool s[maxn];
int n,a,b;

bool OK(int x){
    if(x>0&&x<=n) return true;
    return false;
}

int dijkstra(int Src,int End){
    int i,j,u,tmp;
    for(i=1;i<=n;i++){
        dis[i]=Map[Src][i];
        s[i]=false;
    }
    s[Src]=true;
    dis[Src]=0;
    for(i=1;i<n;i++){
        tmp=inf;
        for(j=1;j<=n;j++){
            if(!s[j]&&dis[j]<tmp){
                tmp=dis[j];
                u=j;
            }
        }
        s[u]=true;
        for(j=1;j<=n;j++){
            if(dis[j]>dis[u]+Map[u][j])
                dis[j]=dis[u]+Map[u][j];
        }
    }
    return dis[End]>=inf?-1:dis[End];
}
int main()
{
    while(scanf("%d",&n),n){
        scanf("%d %d",&a,&b);
        memset(Map,inf,sizeof(Map));
        int x;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            if(OK(i+x)) Map[i][i+x]=1;
            if(OK(i-x)) Map[i][i-x]=1;
        }
        if(a==b){
            printf("0
");
            continue;
        }
        if(!OK(a)||!OK(b)){
            printf("-1
");
            continue;
        }
        printf("%d
",dijkstra(a,b));
    }
    return 0;
}

 HDU 2066  혼자 만 의 여행http://acm.hdu.edu.cn/showproblem.php?pid=2066
제목: 한 사람 이 D 곳 에 가 고 싶 으 면 T 곳 에서 출발 하여 가 고 싶 은 곳 에 도착 하 는 가장 짧 은 시간 을 물 어 볼 수 있다.
문제 풀이: 다 원 최 단 로 이지 만 Folyd 로 시간 을 초과 하여 모든 출발점 에 대해 단원 최 단 로 구법 (Dijkstra) 을 할 수 있 습 니 다.
 
Source Code：
 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=1005;
int Map[maxn][maxn],dis[maxn];
int T,S,D,maxC;
bool mark[maxn];
int start[maxn],want[maxn];

void dijkstra(int src){
    int i,j,u,tmp;
    for(i=1;i<=maxC;i++){
        dis[i]=Map[src][i];
        mark[i]=false;
    }
    dis[src]=0;
    mark[src]=true;
    for(i=1;i<maxC;i++){
        tmp=inf;
        for(j=1;j<=maxC;j++){
            if(!mark[j]&&dis[j]<tmp){
                u=j;
                tmp=dis[j];
            }
        }
        mark[u]=true;
        for(j=1;j<=maxC;j++){
            if(!mark[j]&&dis[j]>dis[u]+Map[u][j])
                dis[j]=dis[u]+Map[u][j];
        }
    }
}

int main()
{
    //freopen("D:\in.txt","r",stdin);
    while(scanf("%d %d %d",&T,&S,&D)==3){
        memset(Map,inf,sizeof(Map));
        maxC=0;
        int a,b,t,ans=inf;
        for(int i=1;i<=T;i++){
            scanf("%d %d %d",&a,&b,&t);
            if(Map[a][b]>t) Map[a][b]=Map[b][a]=t;
            if(a>maxC) maxC=a;
            if(b>maxC) maxC=b;
        }
        for(int i=1;i<=S;i++)
            scanf("%d",&start[i]);
        for(int i=1;i<=D;i++)
            scanf("%d",&want[i]);
        for(int i=1;i<=S;i++){
            dijkstra(start[i]);
            for(int j=1;j<=D;j++)
                if(dis[want[j]]<ans) ans=dis[want[j]];
        }
        printf("%d
",ans);
    }
    return 0;
}

HDU 2112 HDU Today http://acm.hdu.edu.cn/showproblem.php?pid=2112
제목: 출발지 start 에서 목적지 end 까지 의 최 단 거 리 를 구하 세 요.
분석: C + STL 의 map 로 문자열 을 정수 로 바 꾸 는 것 이 전형 적 인 최 단 로 입 니 다.
 
Source Code：

#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

const int N = 155;
const int INF = 99999999;

map<string, int> mp;
map<string, bool> bp;
int way[N][N], dist[N];
bool visit[N];
string begin, end;
int n, ans;

void init()     //     
{
    int i, j;
    mp.clear(); //    mp
    bp.clear(); //    bp
    for(i = 0; i < N; i++)
        for(j = 0; j < N; j++)
            if(i == j) way[i][j] = 0;
            else way[i][j] = INF;
}

void input()    //    
{
    int i, cost;
    ans = 1;
    string str1, str2;
    cin >> begin >> end;
    mp[begin] = 1;      //mp   string 1
    bp[begin] = true;   //bp   string true
    if(!bp[end])
    {
        mp[end] = ++ans;
        bp[end] = true;
    }
    for(i = 1; i <= n; i++)
    {
        cin >> str1 >> str2 >> cost;
        if(!bp[str1])
        {
            mp[str1] = ++ans;
            bp[str1] = true;
        }
        if(!bp[str2])
        {
            mp[str2] = ++ans;
            bp[str2] = true;
        }
        way[mp[str1]][mp[str2]] = way[mp[str2]][mp[str1]] = cost;
    }
}

void spfa()
{
    int i, now;
    memset(visit, false, sizeof(visit));
    for(i = 0; i <= ans; i++) dist[i] = INF;
    dist[1] = 0;
    queue<int> Q;
    Q.push(1);
    visit[1] = true;
    while(!Q.empty())
    {
        now = Q.front();
        Q.pop();
        visit[now] = false;
        for(i = 1; i <= ans; i++)
        {
            if(dist[i] > dist[now] + way[now][i])
            {
                dist[i] = dist[now] + way[now][i];
                if(visit[i] == false)
                {
                    Q.push(i);
                    visit[i] = true;
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d", &n))
    {
        if(n == -1) break;
        init();
        input();
        spfa();
        if(dist[mp[end]] != INF) printf("%d
", dist[mp[end]]);
        else printf("-1
");
    }
    return 0;
}

 
HDU 1217 Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217
제목: 몇 가지 화폐 와 화폐 간 의 환율 을 제시 하고 특정한 화폐 가 다른 화폐 로 바 꾸 어 금 리 를 실현 할 수 있 는 지 물 어 본다 (즉, 원래 의 것 보다 한 바퀴 더 많이 바 꾼 것 이다).
분석: 다 원 최 단 로 는 C + STL map 와 Folyd 를 결합 하여 조금 만 변화 시 키 면 됩 니 다.
 
Source Code：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;

const double inf=0x3f3f3f3f;
const int maxn=50;
map<string,int>mp;
map<string,bool>bp;
bool visit[maxn];
double way[maxn][maxn],dis[maxn];
int n,m,cas=0;
double len;

bool Floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(way[i][j]<way[i][k]*way[k][j])
                    way[i][j]=way[i][k]*way[k][j];
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(way[i][i]>1)
                return true;
        }
    }
    return false;
}
int main()
{
    //freopen("D:\in.txt","r",stdin);
    while(scanf("%d",&n),n){
        string str,str1,str2;
        for(int i=1;i<=n;i++){
            cin>>str;
            mp[str]=i;
        }
        scanf("%d",&m);
        memset(way,0,sizeof(way));
        for(int i=1;i<=m;i++){
            cin>>str1>>len>>str2;
            way[mp[str1]][mp[str2]]=len;
        }
        if(Floyd()) printf("Case %d: Yes
",++cas);
        else        printf("Case %d: No
",++cas);
    }
    return 0;
}

 
 HDU 1535 Invitation Cards http://acm.hdu.edu.cn/showproblem.php?pid=1535
제목: P 개의 사이트 q 노선 이 있 고 두 사이트 사 이 는 단 방향 입 니 다.1 번 사이트 에서 다른 사이트 로 가 는 최 단 로 는 + 다른 사이트 에서 1 번 사이트 로 가 는 최 단 로 의 합 을 구 합 니 다.
분석: 갈 때 다른 사이트 의 단일 소스 최 단 로 의 합 을 구하 면 됩 니 다.돌아 온 것 은 다른 모든 사이트 에서 1 번 사이트 로 가 는 가장 짧 은 길 을 구 하 는 것 입 니 다. 그림 을 역방향 으로 재 구축 하고 1 번 사이트 에서 다른 사이트 로 가 는 가장 짧 은 길 을 구 하 는 것 이 자 연 스 럽 게 생각 할 수 있 습 니 다.
 
Source Code：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=1000001;
const int INF=0x3f3f3f3f;
struct node{
    int v,w,next;
}edgego[N],edgeback[N];
int headgo[N],headback[N],dist[N];
bool mark[N];
int p,q;
void spfa(node edge[],int head[])
{
    memset(mark,false,sizeof(mark));
    for(int i=2;i<=p;i++)
        dist[i]=INF;
    dist[1]=0;
    queue<int>Q;
    Q.push(1);
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        mark[x]=false;
        for(int e=head[x];e!=-1;e=edge[e].next){
            if(dist[edge[e].v]>dist[x]+edge[e].w){
                dist[edge[e].v]=dist[x]+edge[e].w;
                if(!mark[edge[e].v]){
                    mark[edge[e].v]=true;
                    Q.push(edge[e].v);
                }
            }
        }
    }
}
int main()
{
    int t,ans,u,v,w;scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d %d",&p,&q);
        memset(headgo,-1,sizeof(int)*(p+1));
        memset(headback,-1,sizeof(int)*(p+1));
        for(int i=1;i<=q;i++){
            scanf("%d %d %d",&u,&v,&w);
            edgego[i].v=v;
            edgego[i].w=w;
            edgego[i].next=headgo[u];
            headgo[u]=i;

            edgeback[i].v=u;
            edgeback[i].w=w;
            edgeback[i].next=headback[v];
            headback[v]=i;
        }
        spfa(edgego,headgo);
        for(int j=2;j<=p;j++)
            ans+=dist[j];
        spfa(edgeback,headback);
        for(int l=2;l<=p;l++)
            ans+=dist[l];
        printf("%d
",ans);
    }
    return 0;
}