「kuangbin带你飞」专题四最短路专题题解
admin
|
|
269
|
杂项

3247 字
|
1.1 小时

Til the Cows Come Home 板子题

Frogger 求所有1到n的路径中价值最大的边的最小值

Heavy Transportation 求所有1到n的路径中价值最小的边的最大值

Silver Cow Party 起点到终点再到起点的最短路

Currency Exchange SPFA判正环

Wormholes SPFA判负环

MPI Maelstrom 最短路板子题

Cow Contest floyed求传递闭包

Invitation Cards 起点到终点再到起点的最短路

Candies 差分约束板子题

Subway 最短路板子题，但是输入很傻逼

昂贵的聘礼 最短路 + 思维

Tram 板子题

Extended Traffic SPFA跑负权图最短路

Layout 差分约束

 

Til the Cows Come Home

题目描述：

n个点，m条边，问1到n的最短路

思路：

板子题，但是要考虑重边！！！

还有就是POJ不支持万能头

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <double,int> pii;

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int a, b, c;
int tr[1005][1005];

int dis[MAX];
bool vis[MAX];
void dijkstra(){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, inf);dis[1] = 0;
    q.push(m_p(0, 1));
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int v = 1; v <= n; ++v){
            if(dis[v] > dis[u] + tr[u][v]){
                dis[v] = dis[u] + tr[u][v];
                q.push(m_p(dis[v], v));
            }
        }
    }
    cout << dis[n] << endl;
}

void work(){
    cin >> m >> n;
    mem(tr, inf);
    for(int i = 1; i <= m; ++i){
        cin >> a >> b >> c;
        tr[a][b] = tr[b][a] = min(tr[a][b], c);
    }
    dijkstra();
}


int main(){
    work();
    return 0;
}

Frogger

题目描述：

二维平面上有n个点，起点是1，终点是2，问从起点到终点的道路中最大值最小是多少

思路：

用迪杰斯特阿拉维护道路距离的最大值，跑最短路即可

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <double,int> pii;

#define MAX 300000 + 50
#define y1 y114514
int n, m, k;
struct ran{
    double x, y;
}tr[MAX];

double getdis(double x1, double y1, double x2, double y2){
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double dis[205];
bool vis[205];
void dijkstra(){
    mem(vis, 0);
    priority_queue<pii, vector<pii>, greater<pii>>q;
    for(int i = 1; i <= n; ++i)dis[i] = 100000000.0;
    dis[1] = 0;
    q.push(m_p(0, 1));
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int v = 1; v <= n; ++v){
            double d = getdis(tr[u].x, tr[u].y, tr[v].x, tr[v].y);
            if(dis[v] > max(dis[u], d)){
                dis[v] = max(dis[u], d);
                q.push(m_p(dis[v], v));
            }
        }
    }
    printf("Frog Distance = %.3lf\n\n", dis[2]);
    getchar();
}


void work(){
    int tot = 0;
    while (cin >> n && n) {
        printf("Scenario #%d\n", ++tot);
        for(int i = 1; i <= n; ++i){
            cin >> tr[i].x >> tr[i].y;
        }
        dijkstra();
    }
}


int main(){
    work();
    return 0;
}

Heavy Transportation

题目描述：

n个点，m条边，问从1到n的道路中权值最小的边最大是多少

思路：

和第二题差不多，那个题问的是路径中价值最大的边的最小值是多少

这里问的是路径中价值最小的边的最大值

那个题用迪杰斯特拉小根堆维护最大值来跑最短路

这个题用迪杰斯特拉大根堆维护最小值来跑最长路

当然，如果不想考虑到底用大根堆还是小根堆，你可以使用SPFA来写

需要注意的是每次输出完以后要他妈的多输出一个空行

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
void dijkstra(int s, int t){
    mem(vis, 0);
    priority_queue<pii>q;
    mem(dis, 0);
    q.push(m_p(0, s));dis[s] = inf;
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] < min(dis[u] , tr[i].val)){
                dis[v] = min(dis[u] , tr[i].val);
                q.push(m_p(dis[v], v));
            }
        }
    }
    cout << dis[t] << endl << endl;
}

void work(){
    cin >> n >> m;
    mem(head, 0);tot = 0;
    for(int i = 1,a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dijkstra(1, n);
}


int main(){
    io;
    int t;cin >> t;
    for(int p = 1; p <= t; ++p){
        printf("Scenario #%d:\n",p);
        work();
    }
    return 0;
}

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
void SPFA(){
    mem(vis, 0);
    queue<int>q;q.push(1);vis[1] = 1;
    mem(dis, 0);dis[1] = inf;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] < min(dis[u], tr[i].val)){
                dis[v] = min(dis[u], tr[i].val);
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    cout << dis[n] << endl << endl;
}

void work(){
    cin >> n >> m;
    mem(head, 0);tot = 0;
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    SPFA();
}


int main(){
    io;
    int t;cin >> t;
    for(int p = 1; p <= t; ++p){
        printf("Scenario #%d:\n",p);
        work();
    }
    return 0;
}

 

Currency Exchange

题目描述：

n种货币，m种兑换方式，最开始有v个货币s，每种兑换方式有六个数字a b h1 y1 h2 y2，前两种表示货币的种类，h1,h2表示汇率，y1,y2表示佣金，x个a可以得到(x-y1)*h1个b,x个b可以得到(x-y2)*h2个a，问你能不能通过某种方式从中赚到钱

思路：

SPFA跑最长路来判正环

只不过这次不是建边，而是根据汇率和佣金进行计算

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, s;
double v;
int a, b;
double hui[105][105];
double yong[105][105];
vector<int>tr[105];

bool vis[MAX];
double dis[MAX];
int cnt[MAX];
void SPFA(){
    queue<int>q;
    q.push(s);
    mem(dis, 0);
    dis[s] = v;
    vis[s] = 1;
    while (!q.empty()) {
        int u = q.front();q.pop();
        vis[u] = 0;
        for(int i = 0; i < tr[u].size(); ++i){
            int v = tr[u][i];
            if(dis[v] < (dis[u] - yong[u][v]) * hui[u][v]){
                dis[v] = (dis[u] - yong[u][v]) * hui[u][v];
                cnt[v] = cnt[u] + 1;
                if(cnt[v] >= n){
                    cout << "YES\n";
                    return;
                }
                if(!vis[v]){
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    cout << "NO\n";
}

void work(){
    cin >> n >> m >> s >> v;
    for(int i = 1; i <= m; ++i){
        cin >> a >> b;
        cin >> hui[a][b] >> yong[a][b] >> hui[b][a] >> yong[b][a];
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    SPFA();
}


int main(){
    io;
    work();
    return 0;
}

 

Silver Cow Party

题目描述：

n个点，m条有向边，终点为s，每个点i要从i跑到s，再从s跑到i,问所有的点中的最短路的最大值是多少

思路：

反向建边跑一次迪杰斯特拉，再正向建边跑一次迪杰斯特拉，求和取最大值即可

	
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, s;
int tr[1005][1005];
int ar[1005][1005];

int dis1[MAX];
bool vis[MAX];
void dijkstra1(){
    mem(dis1, inf);dis1[s] = 0;
    priority_queue<pii,vector<pii>, greater<pii> >q;
    q.push(m_p(dis1[s], s));
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        for(int v = 1; v <= n; ++v){
            if(dis1[v] > dis1[u] + tr[u][v]){
                dis1[v] = dis1[u] + tr[u][v];
                q.push(m_p(dis1[v], v));
            }
        }
    }
}
int dis2[MAX];
void dijkstra2(){
    mem(vis, 0);
    mem(dis2, inf);dis2[s] = 0;
    priority_queue<pii,vector<pii>, greater<pii> >q;
    q.push(m_p(dis2[s], s));
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        for(int v = 1; v <= n; ++v){
            if(dis2[v] > dis2[u] + ar[u][v]){
                dis2[v] = dis2[u] + ar[u][v];
                q.push(m_p(dis2[v], v));
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, dis1[i] + dis2[i]);
    }
    cout << ans << endl;
}

void work(){
    cin >> n >> m >> s;
    mem(tr, inf);
    mem(ar, inf);
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        tr[a][b] = min(tr[a][b], c);
        ar[b][a] = min(ar[b][a], c);
    }
    dijkstra1();
    dijkstra2();
}


int main(){
    io;
    work();
    return 0;
}

Wormholes

题目描述：

n个点，m条正权值的双向边，k条负权值的单向边，判断是否存在负环

思路：

SPFA判负环的板子题

注意重边

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m1, m2, k;
int a, b, c;
int tr[505][505];
int num[505];
int dis[505];
bool vis[505];
void SPFA(){
    mem(vis, 0);
    mem(num, 0);
    queue<int>q;q.push(1);vis[1] = 1;
    mem(dis, inf);dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int v = 1; v <= n; ++v){
            if(dis[v] > dis[u] + tr[u][v]){
                dis[v] = dis[u] + tr[u][v];
                num[v] = num[u] + 1;
                if(num[v] > n){
                    cout << "YES\n";
                    return;
                }
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    cout << "NO\n";
}

void work(){
    cin >> n >> m1 >> m2;
    mem(tr, inf);
    while (m1--) {
        cin >> a >> b >> c;
        tr[a][b] = tr[b][a] = min(tr[a][b], c);
    }
    while (m2--) {
        cin >> a >> b >> c;
        tr[a][b] = min(tr[a][b], -c);
    }
    SPFA();
}


int main(){
    io;
    int t;cin >> t;
    for(int p = 1; p <= t; ++p){
        work();
    }
    return 0;
}

MPI Maelstrom

题目描述：

给定一个下三角矩阵，问从1开始到其他的最短路的最大值是多少

思路：

因为两个点之间不连通时是x,所以我们需要以字符串的形式读入，判断是不是x,不是的话就将字符串转换成十进制的数

剩下的就是跑最短路的板子了

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
string p;
int tr[105][105];

int fuck(string s){
    int cao = 0;
    for(int i = 0; i < s.size(); ++i){
        cao *= 10;
        cao += s[i] - '0';
    }
    return cao;
}

int dis[105];
bool vis[105];
void dijkstra(){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, inf);dis[1] = 0;
    q.push(m_p(0, 1));
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int v = 1; v <= n; ++v){
            if(dis[v] > dis[u] + tr[u][v]){
                dis[v] = dis[u] + tr[u][v];
                q.push(m_p(dis[v], v));
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, dis[i]);
    }
    cout << ans << endl;
}

void work(){
    cin >> n;
    mem(tr, inf);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j < i; ++j){
            cin >> p;
            if(p == "x")continue;
            tr[j][i] = tr[i][j] = fuck(p);
        }
    }
    dijkstra();
}


int main(){
    io;
    work();
    return 0;
}

Cow Contest

题目描述：

n个牛，m个关系，每个关系a, b表示a比b强，如果a 比b强，b比c强，则a比c强，问有多少头牛可以确定他的排名，也就是问有多少头牛可以和其他的每头牛比能力大小

思路：

floyed求传递闭包，典中典

for(int k = 1; k <= n; ++k){
 for(int i = 1; i <= n; ++i){
     for(int j = 1; j <= n; ++j){
         tr[i][j] |= tr[i][k] & tr[k][j];
     }
 }
}

tr[i][j]=1表示i的能力大于j，所以要想判断这头牛能不能确定关系，就这样：

int ans = 0;
for(int i = 1; i <= n; ++i){
     int p = 1;
     for(int j = 1; j <= n; ++j){
         if(i == j)continue;
         if(tr[i][j] + tr[j][i] != 1){//只有两者之间只存在一个1的时候才能判断这两个人的关系，否则就不能判断
             p = 0;
         }
     }
     ans += p;
 }

 

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int a, b;
int tr[105][105];

void work(){
    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        tr[a][b] = 1;
    }
    for(int k = 1; k <= n; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                tr[i][j] |= tr[i][k] & tr[k][j];
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        int p = 1;
        for(int j = 1; j <= n; ++j){
            if(i == j)continue;
            if(tr[i][j] + tr[j][i] != 1){
                p = 0;
            }
        }
        ans += p;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

Invitation Cards

题目描述：

n个点，m条有向边，起点为1，要从1跑到每个点i，再跑回1，问总的时间

思路：

先正向建图跑一次单源最短路，再反向建图跑一次单源最短路

坑点是卡IO，得用scanf

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
int n, m;
int a, b, c;

struct ranran{
    int a, b, c;
}ar[MAX];

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
void dijkstra(int s){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, inf);
    mem(vis, 0);
    q.push(m_p(0, s));dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                q.push(m_p(dis[v], v));
            }
        }
    }
}

void work(){
    tot = 0;mem(head, 0);
    sdd(n, m);
    for(int i = 1; i <= m; ++i){
        sdd(ar[i].a, ar[i].b);sd(ar[i].c);
        add(ar[i].a, ar[i].b, ar[i].c);
    }
    dijkstra(1);
    ll ans = 0;
    for(int i = 1; i <= n; ++i)ans += dis[i];
    mem(head, 0);tot = 0;
    for(int i = 1; i <= m; ++i){
        add(ar[i].b, ar[i].a, ar[i].c);
    }
    dijkstra(1);
    for(int i = 1; i <= n; ++i)ans += dis[i];
    printf("%lld\n",ans);
}


int main(){
    int tt;sd(tt);
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}

Candies

题目描述：

n个人，m个要求，每个要求包含a b c三个整数，表示小朋友b比小朋友a最多多c个糖果

思路：

差分约束板子题

问最大值，跑最短路，转换成<=的形式

也就是建a->b权值为c的边，以1为起点，跑单源最短路

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
void dijkstra(int s, int t){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, inf);
    q.push(m_p(0, s));dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                q.push(m_p(dis[v], v));
            }
        }
    }
    cout << dis[t] << endl;
}

void work(){
    cin >> n >> m;
//    for(int i = 1; i <= n; ++i){
//        add(i + 1, i, 0);
//    }
    for(int i = 1,a, b, c; i <= m; ++i){
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    dijkstra(1, n);
}


int main(){
    work();
    return 0;
}

Subway

题目描述：

不想多说，就是很简单的板子题，但是输入的方法非常坑，没什么意思

 

昂贵的聘礼

点击这里

 

Tram

题目描述：

题意：有n个点，然后这些点和其他点有些路径，每个点是一个开关，开关只能有一个方向走一条路，而第一个数就是默认的开关指向，不用旋转。就是默认的指向实际上只需要旋转0次，而其他路径只需要旋转1次，无论是哪条，只需1次。求a到b最小的旋转次数

思路：

按照题意建边跑最短路就行，板子题

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>

using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, s, t, k, x;
int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
void dijkstra(int s, int t){
    priority_queue<pii, vector<pii>, greater<pii>>q;
    mem(dis, inf);
    q.push(m_p(0, s));dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second ;q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                q.push(m_p(dis[v], v));
            }
        }
    }
    if(dis[t] == inf)cout << -1 << endl;
    else cout << dis[t] << endl;
}

void work(){
    cin >> n >> s >> t;
    for(int i = 1; i <= n; ++i){
        cin >> k;
        if(!k)continue;
        else if(k == 1){
            cin >> x;
            add(i, x, 0);
        }
        else {
            cin >> x;
            add(i, x, 0);
            while (--k) {
                cin >> x;
                add(i, x, 1);
            }
        }
    }
    dijkstra(s, t);
}


int main(){
    io;
    work();
    return 0;
}

 

Extended Traffic

题目描述：

n个点，每个点都有一个权值a[1],m条边a, b，权值是 ，q次询问，每次询问，问1到x的最短路，如果这个数小于3或者这个点无法到达，则输出?,否则输出最短路

思路：

存在负权边，要用SPFA

坑点是每次输入的时候都有一个空行，开io就别他妈用getchar()

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>

using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int val[205];
int tr[205][205];
bool vis[205];
int dis[205];
int num[205];
void SPFA(){
    mem(vis, 0);mem(num, 0);
    queue<int>q;q.push(1);vis[1] = 1;
    mem(dis, inf);dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int v = 1; v <= n; ++v){
            if(dis[v] > dis[u] + tr[u][v]){
                dis[v] = dis[u] + tr[u][v];
                num[v] = num[u] + 1;
                if(num[v] >= n){
                    return;
                }
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

void work(){
    getchar();
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> val[i];
    }
    cin >> m;
    mem(tr, inf);
    int a, b;
    while (m--) {
        cin >> a >> b;
        tr[a][b] = (val[b] - val[a]) * (val[b] - val[a]) * (val[b] - val[a]);
    }
    SPFA();
    cin >> m;
    while (m--) {
        cin >> b;
        if(dis[b] < 3 || dis[b] >= inf / 2)cout << "?\n";
        else cout << dis[b] << endl;
    }
}


int main(){
    int t;cin >> t;
    for(int p = 1; p <= t; ++p){
        printf("Case %d:\n", p);
        work();
    }
    return 0;
}

Layout

题目描述：

小学生在排队时喜欢靠近他们的朋友。 FJ有N（2 <= N <= 1,000）个编号为1..N的小学生按编号顺序站在一条直线上等待。有些小学生之间关系比较好，所以希望彼此之间不超过一定距离，有些小学生关系比较差，所以希望彼此之间至少满足某个距离。有可能有多个小学生在同一个位置上。现在，给出了ML个关系好的小学生的信息和MD个关系不好的小学生的信息。在满足这些条件的排列方法中，求1号学生和N号学生的最大距离，如果不存在可能的排列方法输出-1，如果距离可以无限大就输出-2.

思路：

差分约束

问最大距离，用最短路，转换成<=号

还是用前缀和来处理，不过这次同一个位置可能有多个奶牛，那我们只需要满足 就行，也就是,就从i+1到i连一条权值为0的边

好基友关系是 ，也就是 ,从a-1到b连一条权值为c的边

情敌关系是sum[b] - sum[a - 1] >= c，也就是 ,从b到a-1连一条权值为-c的边

想好怎么建图了以后，难点有来了，什么时候是-1，什么时候是-2

-1很简答，就是不能满足所有的条件，即建立超级源点后存在负环

出现-2就是说明1和n之间没有关系印象，此时可以放到无限远，也就是说我们只需要把1号点作为源点，看看能不能跑出n的最短路，如果不能就是-2，否则就输出最短路就行

Q：那为什么判-1的时候要建立超级源点，而判-2的时候不需要？

因为判断-1是要满足所有牛的条件，而判-2只是要看1和n之间的距离能否达到无穷大

#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>

using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
int num[MAX];
bool SPFA(int s){
    mem(vis, 0);mem(num, 0);
    queue<int>q;q.push(s);vis[s] = 1;
    mem(dis, inf);dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                num[v] = num[u] + 1;
                if(num[v] >= n)return 0;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}


void work(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i)add(0, i, 0);
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        add(a, b, c);
    }
    for(int i = 1, a, b, c; i <= k; ++i){
        cin >> a >> b >> c;
        add(b, a, -c);
    }
    if(!SPFA(0))cout << -1 << endl;
    else {
        SPFA(1);
        if(dis[n] == inf)cout << -2 << endl;
        else cout << dis[n] << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
图论最短路
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
拓扑排序详解

							
							

							
AtCoder Beginner Contest 244  E – King Bombee 「图论 + dp」

							
							

							
观光奶牛 「二分答案 + SPFA判负环」

							
							

							
F – False God「思维」「图论」「树上最长路」

							
							

							
什么是SPFA？SPFA怎么判负环？怎么判正环？