喵呜的虚拟城市(最短路)

虚拟城市是一个基于Windows平台的2D经营策略游戏。你可以在游戏中建造各种各样的建筑（公园、雕塑、喷泉、小屋、公寓、办公区、商场写字楼、综合办公楼、办公大楼、现代化摩天大楼等）、道路，也可以销毁他们， 当然建造、销毁它们都要花费资金，你可以通过每月的税收赚钱，就像专业的大型策略游戏一样。

第一行输入一个数T，表示测试数据个数，对于每组测试数据，第一行输入两个数n, m(2<=n<=50, 0<=m<=n*(n-1))，表示有n个车站，且这n个车站之间共存在m辆巴士。接下来，输入m行，每行两个数x, y(1<=x, y<=n)，表示x和y之间有一辆巴士，且如果容量满足v(x)>=v(y)时，这辆巴士不会被停运，即可以将人们从x输送至y，但是无论容量怎么变，这辆车是不负责将人们从y输送至x。题目保证x和y不相同，也保证不会有两辆巴士有相同的起点和终点。接下来一行输入n个数，表示初始状态下n个车站的容量。(1<=v(i)<=10^9)

33 41 22 12 33 230 20 102 21 22 110 203 21 22 110 10 10

010-1

#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int maxn = 2500 + 5;
const int maxv = 200000 + 5;
const ll max_dis = 1e18 + 5;

int T;
int n,m,a,b;
int tmap[55][55];
int dist[55];
ll dis[maxn];

struct Edge{
    int to,dis;
    Edge(){}
    Edge(int to,int dis){
        this -> to = to;
        this -> dis = dis;
    }
};
vector<Edge>graph[maxn];

typedef pair<int,int>P;

void init(){
    memset(tmap,0,sizeof(tmap));
    for(int i=0;i<maxn;i++)
        graph[i].clear();
}

void input(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        tmap[a][b]=1;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&dist[i]);
}

//把一个点分成n个点，然后连边
void add(int u,int v){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dist[i]>=dist[j])
                graph[(u-1)*n+i].push_back(Edge((v-1)*n+j,abs(dist[j]-dist[v])));
        }
    }
}

void createGraph(){
    for(int i=1;i<=n;i++){
        graph[0].push_back(Edge(i,abs(dist[i]-dist[1])));
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(tmap[i][j]){
                add(i,j);
            }
        }
    }
}

ll dijkstra(int s){
    fill(dis,dis+maxn,max_dis);
    priority_queue<P,vector<P>,greater<P> >q;
    while(!q.empty()) q.pop();
    dis[s]=0;
    q.push(P(0,s));
    while(!q.empty()){
        P p=q.top();q.pop();
        int u=p.second;
        if(p.first>dis[u]) continue;
        for(int i=0;i<graph[u].size();i++){
            Edge& e=graph[u][i];
            if(dis[e.to]>dis[u]+e.dis){
                dis[e.to]=dis[u]+e.dis;
                q.push(P(dis[e.to],e.to));
            }
        }
    }
    ll ans=max_dis;
    //车站n所形成的点是(n-1)*n+1~n*n
    for(int i=(n-1)*n+1;i<=n*n;i++){
        ans=min(ans,dis[i]);
    }
    if(ans==max_dis) return -1;
    return ans;
}

void solve(){
    createGraph();
    printf("%lld\n",dijkstra(0));
}

int main(){
    //freopen("cin.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        init();
        input();
        solve();
    }return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。