【每日一题】5月14日 maze

题目大意: 的网格，，网格上有一些点不能行走，给定Q个传送门((x1,y1),(x2,y2)),表示点(x1,y1)到点(x2,y2)额外有一条路径耗时为3秒，给定起点与终点，问从起点走到终点的最短时间是多少。

分析:网格上点数为9e4,可以直接跑dij,网格加边和额外的Q条边.注意坐标化点:(x,y)---->点(x-1)*m+y .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define pr pair<int,int>
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1}; 

const int maxn=4e5+10;

struct node{
    int v,len,nxt;
}a[maxn];
bool vis[maxn];
int dis[maxn];
int head[maxn],cnt;

void add( int u,int v,int len )
{
    a[cnt]={ v,len,head[u] };
    head[u]=cnt++;
}

void init()
{
    memset(head,-1,sizeof(head)),cnt=0;
}

void dijkstra( int s ) // 起点 
{ 
    memset( dis,inf,sizeof(dis) );
    memset( vis,0,sizeof(vis) );
    priority_queue<pr,vector<pr>,greater<pr> > q;
    q.push( make_pair(0,s) );
    dis[s]=0;
    while( q.size() ) 
    {
        int u=q.top().second;
        q.pop();
        vis[u]=1;
        for( int i=head[u];~i;i=a[i].nxt )
        {
            int v=a[i].v,len=a[i].len;
            if( !vis[v] && dis[v]>dis[u]+len )
            {
                dis[v]=dis[u]+len;
                q.push( make_pair(dis[v],v) );
            }
        }
    } 
}


char s[500][500];

int main()
{
    int n,m,q;
    while( ~scanf("%d%d%d",&n,&m,&q) )
    {
        init();
        int sx,sy,ex,ey;
        for( int i=1;i<=n;i++ )
        {
            scanf("%s",s[i]+1);
            for( int j=1;j<=m;j++ )
            {
                if( s[i][j]=='S' ) sx=i,sy=j;
                if( s[i][j]=='T' ) ex=i,ey=j;
            }
        }
        for( int i=1;i<=n;i++ )
        {
            for( int j=1;j<=m;j++ )
            {
                if( s[i][j]!='#' )
                {
                    for( int k=0;k<4;k++ )
                    {
                        int nx=i+dx[k],ny=j+dy[k];
                        if( nx<1 || nx>n || ny<1 || ny>m || s[nx][ny]=='#' ) continue;
                        add( (i-1)*m+j,(nx-1)*m+ny,1 );
                    }
                }
            }
        }

        for( int i=1;i<=q;i++ )
        {
            int x1,x2,y1,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            add( x1*m+y1+1,x2*m+y2+1,3);
        }
        dijkstra( (sx-1)*m+sy );
        if( !vis[(ex-1)*m+ey] ) puts("-1");
        else printf("%d\n",dis[ (ex-1)*m+ey ]);
    }
}