最短路项目辅助代码

#define DeBUG
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <set>
#include <sstream>
#include <map>
#include <bitset>
#include <windows.h>
using namespace std ;
#define zero {0}
#define INF 2000000000
#define EPS 1e-6
typedef long long LL;
#define WIDTH 16
#define HEIGHT 10
const double PI = acos(-1.0);
inline int sgn(double x)
{
    return fabs(x) < EPS ? 0 :(x < 0 ? -1 : 1);
}
#define n 80
int mp[n+1][n+1];
const short shop_map[10][16] = {
{ 1, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254
 },
{ 2, 3, 4, 5, 0, 6, 75, 7, 8, 73, 9, 10, 0, 11, 254, 254
 },
{ 39, 254, 254, 254, 254, 254, 52, 254, 254, 58, 254, 63, 254, 11, 0, 66
 },
{ 40, 254, 254, 254, 254, 254, 53, 254, 254, 58, 254, 0, 254, 254, 254, 67
 },
{ 41, 12, 13, 14, 77, 15, 0, 16, 17, 74, 18, 19, 20, 76, 21, 67
 },
{ 42, 254, 254, 254, 47, 254, 54, 254, 254, 59, 254, 254, 254, 64, 254, 68
 },
{ 43, 22, 23, 24, 48, 25, 55, 26, 0, 60, 27, 28, 0, 65, 29, 69
 },
{ 44, 254, 254, 254, 49, 254, 56, 254, 254, 61, 254, 254, 254, 254, 254, 70
 },
{ 45, 30, 31, 32, 50, 33, 57, 34, 0, 62, 35, 36, 37, 0, 38, 71
 },
{ 46, 254, 254, 254, 51, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 72
 }
};
char road[100][100];
/**
 * [Dijkstra description]
 * @param  mp   权值矩阵,从1开始
 * @param  n    点数
 * @param  s    起始点
 * @param  t    终点
 * @param  path 起始点到各点的路(前驱)
 * @return      起点到终点的最短长度
 */
int Dijkstra(int s,int t, int path[])
{
    int i,j,w,minc;
    bool visit[n+1];
    int price[n+1];
    for(i=1; i<=n; i++)
        visit[i]=false;
    for(i=1; i<=n; i++)
    {
        price[i]=mp[s][i];
        path[i]=s;
    }
    visit[s]=true;
    price[s]=0;
    //path[s]=0;
    for(i=1; i<n; i++)
    {
        minc=INF;
        w=0;
        for(j=1; j<=n; j++)
            if((visit[j]==false)&&(minc>=price[j]))
            {
                minc=price[j];
                w=j;
            }
        visit[w]=true;
        for(j=1; j<=n; j++)
            if((visit[j]==false)&&(mp[w][j]!=INF)&&(price[j]>price[w]+mp[w][j]))
            {
                price[j]=price[w]+mp[w][j];
                path[j]=w;
            }
    }
    return price[t];
}
int dir[4][2]= {-1,0,1,0,0,-1,0,1};
void init()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            mp[i][j]=INF;
        }
    }
    memset(road,0,sizeof(road));
    int w;
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<16; j++)
        {
            for(int k=0; k<4; k++)
            {
                w=1;
                int nowx=i;
                int nowy=j;
                if(shop_map[i][j]==254)
                {
                    road[i+1][j+1]='#';
                }
                nowx+=dir[k][0];
                nowy+=dir[k][1];
                while(shop_map[nowx][nowy]==0&&nowx>=0&&nowy>=0&&nowx<HEIGHT&&nowy<WIDTH)
                {
                    w++;
                    nowx+=dir[k][0];
                    nowy+=dir[k][1];
                }
                if(nowx<0||nowy<0||nowx>=HEIGHT||nowy>=WIDTH||shop_map[nowx][nowy]==254)
                    continue;
                int a=shop_map[i][j];
                int b=shop_map[nowx][nowy];
                if(a>=1&&a<=n&&b>=1&&b<=n)
                {
                    mp[a][b]=1;
                    mp[b][a]=1;
                }
            }
        }
    }
}
int main()
{
#ifdef DeBUGs
    //freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
    freopen("C:\Users\Sky\Desktop\dabiao.txt","w",stdout);
#endif
    int m;
    int path[n+1];
    init();
    int s=1;
    int t=7;
    int value=Dijkstra(s,t,path);


//////////////生成地图权值数据
    // printf("%d
", n);
    // printf("{");
    // for(int i=0;i<n;i++)
    // {
    //     printf("{" );
    //     printf("%d", mp[i][0]);
    //     for(int j=1;j<n;j++)
    //     {
    //         printf(",%d",mp[i][j]==INF?-1:mp[i][j]);
    //     }
    //     printf("},
");
    // }
    // printf("};");
    

/////////测试用
    for(int i=1; i<=n; i++)
    {
        int k=i;
        char nowroad[100][100];
        memcpy(nowroad,road,sizeof(nowroad));
                nowroad[1][1]='*';
        while(k!=s)
        {
            //printf("%d<--",k);
            for(int i=0;i<10;i++)
                for(int j=0;j<16;j++)
                {
                    if(shop_map[i][j]==k)
                    {
                        nowroad[i+1][j+1]='*';
                    }
                }
            k=path[k];
        }
        printf("--------------------  %d
",i);
        for(int i=1;i<=HEIGHT;i++)
        {
            for(int j=1;j<=WIDTH;j++)
            {
                printf("%c", nowroad[i][j]);
            }
            printf("
");
        }
        Sleep(1000);
        //printf("%d
",s);
    }
    printf("%d
", value);
    return 0;
}