[编程题]I Wanna Go Home
- 热度指数：9491 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
The country is facing a terrible civil war----cities in the country are divided into two parts supporting different leaders. As a merchant, Mr. M does not pay attention to politics but he actually knows the severe situation, and your task is to help him reach home as soon as possible.
"For the sake of safety,", said Mr.M, "your route should contain at most 1 road which connects two cities of different camp."
Would you please tell Mr. M at least how long will it take to reach his sweet home?
输入描述:
The input contains multiple test cases. The first line of each case is an integer N (2<=N<=600), representing the number of cities in the country. The second line contains one integer M (0<=M<=10000), which is the number of roads. The following M lines are the information of the roads. Each line contains three integers A, B and T, which means the road between city A and city B will cost time T. T is in the range of [1,500]. Next part contains N integers, which are either 1 or 2. The i-th integer shows the supporting leader of city i. To simplify the problem, we assume that Mr. M starts from city 1 and his target is city 2. City 1 always supports leader 1 while city 2 is at the same side of leader 2. Note that all roads are bidirectional and there is at most 1 road between two cities. Input is ended with a case of N=0.
输出描述:
For each test case, output one integer representing the minimum time to reach home. If it is impossible to reach home according to Mr. M's demands, output -1 instead.
示例1
输入
2 1 1 2 100 1 2 3 3 1 2 100 1 3 40 2 3 50 1 2 1 5 5 3 1 200 5 3 150 2 5 160 4 3 170 4 2 170 1 2 2 2 1 0
输出
100 90 540
#include <iostream>
#include <fstream>
using namespace std;
#define INF 9999999
const int maxn = 610;
const int maxm = 10010;
int n;
int G[maxn][maxn];
int leader[maxn];
void floyd(){
for(int k = 1; k <= n; ++k){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(G[i][j] > G[i][k] + G[k][j]){
G[i][j] = G[i][k] + G[k][j];
}
}
}
}
}
int main(){
int m, a, b, c;
// freopen("a.txt", "r", stdin);
while(cin >> n >> m && n != 0){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i == j) G[i][j] = 0;
G[i][j] = INF;
}
}
for(int i = 0; i < m; ++i){
cin >> a >> b >> c;
if(G[a][b] > c){
G[a][b] = G[b][a] = c; //20%的未通过案例来自这句
}
}
for(int i = 1; i <= n; ++i){
cin >> leader[i];
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
//只要把不在一个阵营的边设置成有向边即可：leader1->deader2通，leader2->leader1不通
if(leader[i] == 2 && leader[j] == 1){
G[i][j] = INF;
}
}
}
floyd();
if(G[1][2] == INF) cout << "-1" << endl;
else cout << G[1][2] << endl;
}
return 0;
}
发表于 2018-08-17 21:02:55
回复(8)
/*一开始没读懂题目，不明白那行1212之类的是干嘛的，后来才看见题目中有个最多只能转变1次阵营的限制
，由题意可知，M出发地是1号，目的地总是2号，从1-2必须转变一次阵营，所以就要求在这之前不能出现2-1的
情况，出现了就不符合题目的要求，所以就在Dijkstra中判断松弛条件的时候加一个判断语句就能求解了*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 601;
const int INF = 0x3f3f3f3f;
struct Edge{
int to;
int length;
Edge(int t, int l): to(t), length(l) {}
};
struct Point{
int number;
int distance;
Point(int n, int d): number(n), distance(d) {}
bool operator< (const Point& p) const{
return distance > p.distance;
}
};
vector<Edge> g[MAXN];
int dis[MAXN];
int arr[MAXN];
void Dijkstra(int s){ //优先队列优化的Dijkstra算法
priority_queue<Point> PQ;
dis[s] = 0;
PQ.push(Point(s, dis[s]));
while(!PQ.empty()){
int u = PQ.top().number;
PQ.pop();
for(int i = 0; i < g[u].size(); ++i){
int v = g[u][i].to;
int l = g[u][i].length;
if(!(arr[u-1] == 2 && arr[v-1] == 1) && (dis[v] > dis[u] + l)){
dis[v] = dis[u] + l;
PQ.push(Point(v, dis[v]));
}
}
}
}
int main(){
int n, m;
while(cin >> n && n){
cin >> m;
memset(g, 0, sizeof(g));
memset(dis, 0x3f, sizeof(dis));
for(int i = 0; i < m; ++i){
int from, to, length;
cin >> from >> to >> length;
g[from].push_back(Edge(to, length));
g[to].push_back(Edge(from, length));
}
for(int i = 0; i < n; ++i){
cin >> arr[i];
}
Dijkstra(1);
if(dis[2] == INF){
cout << "-1" << endl;
}
else{
cout << dis[2] << endl;
}
}
return 0;
}
发表于 2020-03-27 15:55:26
回复(6)
测试用例有问题，两个城市之间可能有多条路径
我的思路是用dijkstra，更新路径时加个约束--不能从2阵营到1阵营
//============================================================================
// Name : 2017-06-20-02.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 1000000000;
int G[601][601];
bool vis[601];
int d[601];
int camp[601];
int n,m;
int sCamp,tCamp;
void dijkstra(int S, int T){
d[S] = 0;
vis[S] = true;
for(int i=1;i<=n;i++){
if(G[S][i]!=INF){
d[i] = G[S][i];
}
}
for(int i=1;i<=n;i++){
int _u = -1;
int minD = INF;
int _i;
//找到距离S最小 未被访问的点
for(_i=1;_i<=n;_i++){
if(vis[_i]==false && d[_i]<minD){
_u = _i;
minD = d[_i];
}
}
//不连通 或 已找到目标 返回
if(_u==-1 || _u==T){
return;
}
vis[_u] = true;
// 更新距离
for(_i=1;_i<=n;_i++){
//未被访问 && !(camp[_u]==2&&camp[_i]==1) && 过_u能使距离减小
if(vis[_i]==false && !(camp[_u]==tCamp&&camp[_i]!=tCamp) && d[_u]+G[_u][_i]<d[_i]){//&& !(camp[_u]==2&&camp[_i]==1)
d[_i] = d[_u]+G[_u][_i];
}
}
}
}
int main() {
while(1){
fill(G[0],G[0]+601*601,INF);
fill(vis,vis+601, false);
fill(d,d+601,INF);
scanf("%d",&n);
if(n==0){
break;
}
scanf("%d",&m);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c<G[a][b]){
G[a][b] = c;
G[b][a] = c;
}
}
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
camp[i]=a;
}
sCamp = camp[1];
tCamp = camp[2];
dijkstra(1,2);
if(d[2]==INF){
printf("-1\n");
}else{
printf("%d\n",d[2]);
}
}
return 0;
}
发表于 2017-06-21 13:46:34
回复(3)
/*
很显然因为1，2两人必不是一个阵营的,所以题中说最多经过一条不是同一阵营的边,
那么必须是要经过一条的
！！！知道了必须要经过一条之后,因为题目中最多有1e4条边，点很少,
可以考虑用dijksta先求出1 2 到各自阵营的最短距离,然后枚举那条不是同一阵
营的边维护答案的最小值即可，
*/
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pb push_back
#define mk make_pair
using namespace std;
const int maxm = 1e4+5;
const int maxn = 6e2+5;
int n,m;
int book[maxn];
vector<int>v1,v2;
vector<pair<int,int> >edge[maxn];
int d1[maxn],d2[maxn];
void dij1()
{
bool vis[maxn];
for(int i = 0;i < maxn;++i)
{
vis[i] = 0;
d1[i] = inf;
}
d1[1] = 0;
for(int i = 0;i < v1.size();++i)
{
int mi = inf,u = -1;
for(int j = 0;j < v1.size();++j)
{
int v = v1[j];
if(vis[v]) continue;
if(mi > d1[v])
{
mi = d1[v],u = v;
}
}
if(u == -1) break;
vis[u] = 1;
for(int j = 0;j < edge[u].size();++j)
{
int to = edge[u][j].first;
int cos = edge[u][j].second;
if(book[to] == 2) continue;
if(d1[to] > d1[u] + cos)
{
d1[to] = d1[u] + cos;
}
}
}
return ;
}
void dij2()
{
bool vis[maxn];
for(int i = 0;i < maxn;++i)
{
d2[i] = inf;
vis[i] = 0;
}
d2[2] = 0;
for(int i = 0;i < v2.size();++i)
{
int mi = inf,u = -1;
for(int j = 0;j < v2.size();++j)
{
int v = v2[j];
if(vis[v]) continue;
if(mi > d2[v])
{
mi = d2[v],u = v;
}
}
if(u == -1) continue;
vis[u] = 1;
for(int j = 0;j < edge[u].size();++j)
{
int to = edge[u][j].first;
int cos = edge[u][j].second;
if(book[to] == 1) continue;
if(d2[to] > d2[u] + cos)
{
d2[to] = d2[u] + cos;
}
}
}
return ;
}
int main()
{
while(~scanf("%d",&n))
{
memset(book,0,sizeof book);
if(n == 0) break;
scanf("%d",&m);
v1.clear(),v2.clear();
v1.pb(1),v2.pb(2);
for(int i = 0;i < maxn;++i)
edge[i].clear();
for(int i = 0;i < m;++i)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
edge[a].pb(mk(b,c));
edge[b].pb(mk(a,c));
}
for(int i = 1;i <= n;++i)
{
int x;
scanf("%d",&x);
book[i] = x;
if(x == 1)
v1.pb(i);
if(x == 2)
v2.pb(i);
}
dij1(),dij2();
int mi = inf;
for(int i = 0;i < v1.size();++i)
{
int u = v1[i];
for(int j = 0;j < edge[u].size();++j)
{
int to = edge[u][j].first;
int cos = edge[u][j].second;
if(book[u] == book[to]) continue;
mi = min(mi,cos + d1[u] + d2[to]);
}
}
/*for(int i = 0;i < v1.size();++i)
printf("%d %d\n",v1[i],d1[v1[i]]);
puts("debug");
for(int i = 0;i < v2.size();++i)
printf("%d %d\n",v2[i],d2[v2[i]]);*/
if(mi == inf)
puts("-1");
else
printf("%d\n",mi);
}
return 0;
}
编辑于 2018-04-28 22:52:39
回复(0)
#include<stdio.h>
#include<vector>
#define N 601
#define M 10001
using namespace std;
struct E{
int next;
int time;
};
vector<E> edge[M];
bool mark[N];
int dis[N];
int leader[N];
bool cmp(E a,E b){
return a.time<b.time;
}
int main(){
int m,n;
while(scanf("%d",&n)!=EOF&&n!=0){
scanf("%d",&m);
int i,j;
int a,b,t;
for(i=1;i<=N;i++)
edge[i].clear();
while(m--){
scanf("%d%d%d",&a,&b,&t);
E tmp;
tmp.time=t;
tmp.next=b;
edge[a].push_back(tmp);
tmp.next=a;
edge[b].push_back(tmp);
}
for(i=1;i<=n;i++){
mark[i]=false;
dis[i]=-1;
scanf("%d",&leader[i]);
}
int newP=1;
dis[1]=0;
mark[1]=true;
int next,time;
for(i=1;i<n;i++){
for(j=0;j<edge[newP].size();j++){
next=edge[newP][j].next;
time=edge[newP][j].time;
if(leader[newP]==2&&leader[next]==1||mark[next]==true) continue;
if(dis[next]==-1||dis[next]>dis[newP]+time){
dis[next]=dis[newP]+time;
}
}
int min=123123123;
for(j=1;j<=n;j++){
if(mark[j]!=true&&dis[j]!=-1&&dis[j]<min){
min=dis[j];
newP=j;
}
}
mark[newP]=true;
}
printf("%d\n",dis[2]);
}
return 0;
}
发表于 2018-01-24 00:25:23
回复(1)
说好的,两个城市之间只有至多一条路的呢?(你仿佛在逗我,假装有表情包)
import java.util.Scanner;
/*
* QQ: 825580813(一起来敲代码)
* 思路:
* 1,最短路径的修改版
* 2,添加一个标记数组,判断走到当前城市是否已经穿越了两个阵营
*/
public class IWannaGoHome {
static int n, m;
static int[][] graph;
static int[] camp;
static final int max = 1000000;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while ((n = sc.nextInt()) != 0) {
m = sc.nextInt();
graph = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
graph[i][j] = i != j ? max : 0;
}
}
for (int i = 0; i < m; ++i) {
int start = sc.nextInt();
int end = sc.nextInt();
int time = sc.nextInt();
if (time < graph[start - 1][end - 1]) {
graph[start - 1][end - 1] = graph[end - 1][start - 1] = time;
}
}
camp = new int[n];
for (int i = 0; i < n; ++i) {
camp[i] = sc.nextInt();
}
int res = getMinTime();
System.out.println(res);
}
sc.close();
}
private static int getMinTime() {
int[] minTime = new int[n]; // 最少花费时间
boolean[] flag = new boolean[n]; // 是否穿过两个阵营
boolean[] walked = new boolean[n];// 该城市是否走过
for (int i = 1; i < n; ++i) {
minTime[i] = max;
}
minTime[0] = 0;
int start = 0;
int curMin = max;
for (int i = 0; i < n; ++i) {
curMin = max;
for (int j = 0; j < n; ++j) {
if (!walked[j] && curMin > minTime[j]) {
curMin = minTime[j];
start = j;
}
}
walked[start] = true;
if (start == 1) {
return curMin;
}
for (int j = 0; j < n; ++j) {
if (!walked[j] && curMin + graph[start][j] < minTime[j]) {
if (flag[start]) { //如果走到start城市已经穿越了两个阵营
if (camp[start] == camp[j]) { //只能走与start相同的阵营
minTime[j] = curMin + graph[start][j];
flag[j] = true; //并且j阵营也被纳入已穿越的阵营
}
} else { //如果走到start城市还没穿越了两个阵营
minTime[j] = curMin + graph[start][j]; //那么都可以走到j城市
if (camp[start] != camp[j]) { //如果start与j的阵营不同,
flag[j] = true; //那么j阵营就被纳入穿越的阵营
}
}
}
}
}
return minTime[1] == max ? -1 : minTime[1];
}
}
发表于 2017-05-25 16:37:39
回复(1)
最多只能有一条边横跨两个阵营，也就是说只进不出，因此将同阵营的边设置成双向，跨阵营设置成1->2单向。
其他就是再写一遍dijkstra
#include <cstdio>
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
class adjListGraph{
private:
struct edgeNode{
int end;
int weight;
edgeNode *next;
edgeNode(int e,int w,edgeNode *n):end(e),weight(w),next(n){};
};
struct verNode{
int ver;
edgeNode *head;
verNode(edgeNode *h=NULL):head(h){};
};
int Vers,Edges;
verNode *verList;
public:
adjListGraph(int v):Vers(v),Edges(0){
verList = new verNode[Vers];
}
~adjListGraph(){};
void insert(int x,int y,int w);
void dijkstra(int start, int end);
};
void adjListGraph::insert(int x,int y,int w){
verList[x].head = new edgeNode(y,w,verList[x].head);
Edges++;
}
void adjListGraph::dijkstra(int start, int end){
int *dis = new int[Vers];
int *prev = new int[Vers];
bool *known = new bool[Vers];
edgeNode *p;
int min,u;
for(int i = 0; i < Vers; i++){
dis[i] = INT_MAX;
known[i] = false;
}
dis[start] = 0;
prev[start] = start;
for(int i = 0; i < Vers; i++){
min = INT_MAX;
for(int j = 0; j < Vers; j++){
if(!known[j] && dis[j] < min){
min = dis[j];
u = j;
}
}
known[u] = true;
for(p = verList[u].head; p!=NULL; p=p->next){
if(!known[p->end] && dis[p->end] > min + p->weight){
dis[p->end] = min + p->weight;
prev[p->end] = u;
}
}
}
if(dis[end] == INT_MAX) printf("-1\n");
else printf("%d\n", dis[end]);
}
struct edge{
int begin;
int end;
int weight;
edge(int a, int b, int w):begin(a),end(b),weight(w){};
};
int main(){
int n,m;
while(scanf("%d\n", &n) != EOF){
if(n == 0) return 0;
vector<edge> vt;
adjListGraph G(n);
scanf("%d\n", &m);
for(int i = 0; i < m; i++){
int x,y,w;
scanf("%d%d%d\n",&x,&y,&w);
vt.push_back(edge(x-1,y-1,w));
}
int *camp = new int[n];
for(int i = 0; i < n; i++){
scanf("%d",&camp[i]);
}
for(vector<edge>::iterator it=vt.begin(); it!=vt.end(); it++){
if(camp[it->begin] == camp[it->end]){
G.insert(it->begin,it->end,it->weight);
G.insert(it->end,it->begin,it->weight);
} else if(camp[it->begin] == 1){
G.insert(it->begin,it->end,it->weight);
} else{
G.insert(it->end,it->begin,it->weight);
}
}
G.dijkstra(0,1);
}
return 0;
}
发表于 2022-03-04 17:24:22
回复(0)
使用堆(优先队列)优化的Dijkstra算法，时间复杂度O(ElogV)，注释写的很清楚，不喜欢用全局变量
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct edge
{
int end, time;
edge(int e, int t) : end(e), time(t) {};
};
struct point
{
int name, dist,leader;
point(int n, int d,int l) :name(n), dist(d),leader(l) {}
bool operator<(const point& p)const//用于构造小根堆时比较
{
return this->dist > p.dist;
}
};
void Dijkstra(vector<edge>*& road, vector<point>& city, int& n)
{
priority_queue<point> PQ;//小根堆，每轮从当前最近的点开始
PQ.push(city[1]);//起点入堆
while (!PQ.empty())
{
int current = PQ.top().name;
PQ.pop();
for (unsigned int i = 0; i < road[current].size(); i++)//检查起点是current的边
{
edge temp = road[current][i];
int end = temp.end;
int cost = temp.time + city[current].dist;
//不能改变两次阵营
if (city[current].leader == 2 && city[end].leader == 1)
continue;
//如果从current到达end的时间比之前路径到达end的时间短，就走这条路
if (cost < city[end].dist)
{
city[end].dist = cost;
PQ.push(city[end]);
}
}
}
}
int main()
{
int n, m;
while (cin >> n && n != 0)
{
vector<edge>* road = new vector<edge>[n + 1];//1~n，向量数组模拟邻接表
cin >> m;
for (int i = 0; i < m; i++)//输入道路
{
int s, e, t;
cin >> s >> e >> t;
road[s].push_back(edge(e, t));
road[e].push_back(edge(s, t));//无向边，将反向也存进去便于操作
}
vector<point> city;
city.push_back(point(0, 0xfffffff, 0));//占住city[0]位,便于后面操作
for (int i = 1; i <= n; i++)//输入city
{
int l;
cin >> l;
city.push_back(point(i, 0xfffffff, l));//初始都设为不可达
}
city[1].dist = 0;//起点到自己的距离为0
Dijkstra(road, city, n);
if (city[2].dist == 0xfffffff)
cout << -1 << endl;
else
cout << city[2].dist << endl;
city.clear();
}
return 0;
}
编辑于 2020-07-04 11:03:05
回复(0)
本题比较特殊，只有1和2两个阵营，可以直接加一个不准从2->1的限制条件；
但是如果多个阵营的话，就要用通法了.
#include <bits/stdc++.h>
using namespace std;
const int MAXN=605;
const int INF=INT_MAX/10;
struct Edge{
int to;
int length;
Edge(int t,int l):to(t),length(l){}
};
vector<Edge>graph[MAXN];
int dis[MAXN];
int flag[MAXN];
struct Point{
int num;
int distance;
int time;//记录每个点从头开始变化的次数
Point(int n,int d,int t):num(n),distance(d),time(t){}
bool operator<(const Point& c)const{
return distance>c.distance;
}
};
void Dijikstra(int x)
{
int change=0;
dis[x]=0;
priority_queue<Point>myqueue;
myqueue.push(Point(x,dis[x],0));
while(!myqueue.empty())
{
Point T=myqueue.top();
int u=myqueue.top().num;
myqueue.pop();
for(int i=0;i<graph[u].size();i++)
{
int v=graph[u][i].to;
int l=graph[u][i].length;
Point next=T; //每一次进入，都是基于上一个状态的值的变化,是先保存后，不断更新的.
if(dis[v]>dis[u]+l)
{
if(flag[v]!=flag[u]) next.time++;
if(next.time<=1)
{
dis[v]=dis[u]+l;
myqueue.push(Point(v,dis[v],next.time));
}
}
}
}
return ;
}
int main()
{
int n,m;
while(cin>>n>>m)
{
memset(graph,0,sizeof(graph));
fill(dis,dis+n+1,INF);
memset(flag,0,sizeof(flag));
for(int i=1;i<=m;i++)
{
int from,to,length;
scanf("%d%d%d",&from,&to,&length);
graph[from].push_back(Edge(to,length));
graph[to].push_back(Edge(from,length));
}
for(int i=1;i<=n;i++)//归属部落
{
int x; cin>>x;
flag[i]=x;
}
Dijikstra(1);
if(dis[2]==INF) cout<<-1<<endl;
else cout<<dis[2]<<endl;
}
return 0;
}
发表于 2020-04-13 12:50:03
回复(0)
最小生成树加优先队列，但这道题难在只能有一条连接不同阵营的道路，由于一开始是一阵营，最终是而阵营，所以说就不存在从而阵营到一阵营的路，记得符合这个条件就可以了
#include<iostream>
(720)#include<cstring>
#include<queue>
(789)#include<algorithm>
#include<cstdio>
(802)#include<vector>
#include<limits.h>
(1124)#define INF INT_MAX
using namespace std;
struct City{
int to;
int len;
City(int y,int l):to(y),len(l){}
bool operator< (const City& other)const {
return len>other.len;
}
};
vector<City> G[601];
int leader[601];
int dis[601];
int N,M; //N是城市数目，M是道路数目
void Dijstral(){
dis[1]=0;
priority_queue<City> myQueue;
myQueue.push(City(1,0));
while(!myQueue.empty()){
int u=myQueue.top().to;
myQueue.pop();
for(int i=0;i<(int)G[u].size();i++){
int v=G[u][i].to;
if(!(leader[v]==1&&leader[u]==2)&&dis[v]>dis[u]+G[u][i].len){
dis[v]=dis[u]+G[u][i].len;
myQueue.push(City(v,dis[v]));
}
}
}
}
int main(){
while(scanf("%d%d",&N,&M)!=EOF){
if(N==0) break;
memset(G,0,sizeof(G));
fill(dis+1,dis+1+N,INF);
int x,y,len;
for(int i=0;i<M;i++){
scanf("%d%d%d",&x,&y,&len);
G[x].push_back(City(y,len));
G[y].push_back(City(x,len));
}
for(int i=1;i<=N;i++)
scanf("%d",&leader[i]);
Dijstral();
if(dis[2]!=INF)
printf("%d\n",dis[2]);
else
printf("-1\n");
}
return 0;
}
发表于 2020-03-26 12:29:51
回复(0)
看了这么多答案，发现我的思路还是比较独特的： 在Dijkstra的基础上，把穿越阵营也看成一种距离花费，和dis数组类似，在cost[t]小于2的情况下求最短路径即可，有点类似DFS的剪枝。思路想好，代码写出来，改了几处编译错误就直接AC了，果然Dijkstra对于没有负权边的路径问题还是很强大的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<climits>
#include<queue>
using namespace std;
const int MAXN = 605, MAXM = 20005, INF = INT_MAX;
struct enode {
int from, to, dis, op = 0;
enode(int f = -1, int t = -1, int d = -1) :from(f), to(t), dis(d) {}
}road[MAXM];
struct vnode {
int num, dis;
vnode(int n, int d) :num(n), dis(d) {}
bool operator<(vnode x) const {
return dis < x.dis;
}
};
vector<enode> graph[MAXN];
int dis[MAXN], cost[MAXN], camp[MAXN];
void Dijkstra(int s) { //在标准Dijksta上多加了一个cost数组，与dis数组类似一并维护
priority_queue<vnode> que;
que.push(vnode(s, 0));
cost[s] = 0;
dis[s] = 0;
while (!que.empty()) {
int p = que.top().num;
que.pop();
for (int i = 0; i < graph[p].size(); i++) {
int t = graph[p][i].to, d = graph[p][i].dis, c = graph[p][i].op;
if (cost[p] + c > 1 || dis[t] < dis[p] + d) continue;
dis[t] = dis[p] + d; //两种情况下跳过该边：cost大于1或比已有路径更长
cost[t] = cost[p] + c; //更新dis[t] 和 cost[t]
que.push(vnode(t, dis[t]));
}
}
}
int main() {
int n, m, a, b, c;
while (scanf("%d", &n) != EOF) {
if (!n) break;
int edgeNum = 0;
memset(graph, 0, sizeof(graph));
fill(dis, dis + n + 1, INF);
fill(cost, cost + n + 1, INF);
scanf("%d", &m);
for (int i = 0; i < m; i++) { //输入花了点脑筋，还是先储存边然后再更新op值
scanf("%d%d%d", &a, &b, &c);
if (a == b) continue;
road[edgeNum++] = enode(a, b, c);
road[edgeNum++] = enode(b, a, c);
}
for (int i = 1; i <= n; i++) scanf("%d", &camp[i]);
for (int i = 0; i < edgeNum; i++) {
int a = road[i].from, b = road[i].to; //若相反阵营则边的op值为1
if (camp[a] != camp[b])
road[i].op = 1;
graph[a].push_back(road[i]);
}
Dijkstra(1);
if (cost[2] > 1) dis[2] = -1; //判断cost[2] > 1即可涵盖全部情况
printf("%d\n", dis[2]);
}
return 0;
}
编辑于 2020-03-22 20:02:31
回复(0)
/*单源最短路径，因此我首选的是迪杰斯特拉，利用最多只能跨越一次势力来限制Dj中更新最短路径数组。
在使用迪杰斯特拉的时候，因为城市1属于一号势力，城市2属于二号势力，所以在更新d[ ]时判断一下中间点属于哪一方势力就可对路径进行限制。u为中间点，v为待更新点，若u属于一号势力，则v无限制，若u属于二号势力，则v只能属于二号势力*/
# include <stdio.h>
# include <algorithm>
using namespace std;
const int maxn=610;
const int INF =999999;
int n,m;
int G[maxn][maxn]; //G[i][j]表示i j之间的路径长度
int d[maxn]; //d[i]表示 城市1到城市i的最短路径
int city[maxn]; //记录该城市 属于哪个势力
bool vis[maxn];
# include <algorithm>
using namespace std;
const int maxn=610;
const int INF =999999;
int n,m;
int G[maxn][maxn]; //G[i][j]表示i j之间的路径长度
int d[maxn]; //d[i]表示 城市1到城市i的最短路径
int city[maxn]; //记录该城市 属于哪个势力
bool vis[maxn];
void Dj(int s) {
fill(vis,vis+maxn,false);
fill(d,d+maxn,INF);
d[s]=0;
for(int i=1; i<=n; i++) {
int u=-1,min=INF;
for(int j=1; j<=n; j++) {
if(vis[j]==false&&d[j]<min) {
u=j;
min=d[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int v=1; v<=n; v++) {
if(city[u]==1) { //在更新d[ ]时要注意限制条件
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]) //若u属于一号势力则 v可以属于任意一方
d[v]=d[u]+G[u][v];
} else if(city[u]==2) { //若u属于二号势力，则v只能属于二号势力
fill(vis,vis+maxn,false);
fill(d,d+maxn,INF);
d[s]=0;
for(int i=1; i<=n; i++) {
int u=-1,min=INF;
for(int j=1; j<=n; j++) {
if(vis[j]==false&&d[j]<min) {
u=j;
min=d[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int v=1; v<=n; v++) {
if(city[u]==1) { //在更新d[ ]时要注意限制条件
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]) //若u属于一号势力则 v可以属于任意一方
d[v]=d[u]+G[u][v];
} else if(city[u]==2) { //若u属于二号势力，则v只能属于二号势力
//否则 则会穿过两次不同的势力
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]&&city[v]==2)
d[v]=d[u]+G[u][v];
}
}
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]&&city[v]==2)
d[v]=d[u]+G[u][v];
}
}
}
}
int main() {
int a,b,c;
int i,j;
fill(G[0],G[0]+maxn*maxn,INF);
while(scanf("%d%d",&n,&m)!=EOF) {
if(n==0)
break;
for(i=0; i<m; i++) {
scanf("%d%d%d",&a,&b,&c);
if(c<G[b][a]) //沙雕测试用例会出现 两个城市有多条道路的情况，要取小边
G[a][b]=G[b][a]=c;
}
for(j=1; j<=n; j++) {
scanf("%d",&city[j]);
}
Dj(1);
if(d[2]!=INF)
printf("%d\n",d[2]);
else
printf("-1\n");
fill(G[0],G[0]+maxn*maxn,INF);
}
return 0;
return 0;
}
发表于 2020-03-19 18:22:54
回复(0)
#include <bits/stdc++.h>
using namespace std;
class Edge {
public:
int to;
int length;
Edge(int to, int length) : to(to), length(length) {}
// 重载
bool operator==(const Edge &x) {
return x.to == to;
}
};
class Point {
public:
int number;
int distance;
Point(int number, int distance) : number(number), distance(distance) {}
// 从小到大排列
bool operator<(const Point &p) const {
if (distance == p.distance) {
return number < p.number;
}
return distance > p.distance;
}
};
vector<Edge> graph[605];//邻接表，边用vector存，顶点用数组存
vector<int> Dijkstra(int s, vector<int> camps) {
priority_queue<Point> queue;
vector<int> dist(605);
fill(dist.begin(), dist.end(), INT_MAX);
dist[s] = 0;
queue.push(Point(s, dist[s]));
while (!queue.empty()) {
int u = queue.top().number;
queue.pop();
for (int i = 0; i < graph[u].size(); ++i) {
int v = graph[u][i].to;
if (find(camps.begin(), camps.end(), v) != camps.end()) { // 若不是同一阵营，则跳过
int d = graph[u][i].length;
if (dist[v] > dist[u] + d) {
dist[v] = dist[u] + d;
queue.push(Point(v, dist[v]));
}
}
}
}
return dist;
}
//先用两次dijkstra算法，分别求出1、2到同阵营各城市的最短路径长度，结果分别存在d1[N]、d2[N]。
//再遍历穿越边境的边，比方说<i, j>穿越边境且i、j分别属于阵营1、阵营2，G[i][j]是i到j的距离，
// 那么G[i][j]+d1[i]+d2[j]就是从这条路过境的总路径长度。找出这类路径长度里最短的那条，输出即可
int main() {
int n, m;
while (cin >> n) {
if (n == 0) break;
vector<int> camp1;
vector<int> camp2;
cin >> m;
memset(graph, 0, sizeof(graph));
for (int i = 0; i < m; ++i) {
int from, to, weight;
cin >> from >> to >> weight;
if (from == to) continue;
// 测试用例里有重边
vector<Edge> ve1 = graph[from];
Edge edge1(to, 0);
vector<Edge>::iterator pos1 = find(ve1.begin(), ve1.end(), edge1);
// ！！！！！！pos1->length = ... 将并不能改变graph中的值！！！！！
if (pos1 != ve1.end()) graph[from][pos1 - ve1.begin()].length = min(pos1->length, weight);
else graph[from].push_back(Edge(to, weight));
vector<Edge> ve2 = graph[to];
Edge edge2(from, 0);
vector<Edge>::iterator pos2 = find(ve2.begin(), ve2.end(), edge2);
// ！！！！！！pos2->length = ... 将并不能改变graph中的值！！！！！
if (pos2 != ve2.end()) graph[to][pos2 - ve2.begin()].length = min(pos2->length, weight);
else graph[to].push_back(Edge(from, weight));
}
for (int i = 0; i < n; ++i) {
int camp = 0;
cin >> camp;
if (camp == 1) camp1.push_back(i + 1);
else camp2.push_back(i + 1);
}
//先用两次dijkstra算法，分别求出1、2到同阵营各城市的最短路径长度，结果分别存在d1[N]、d2[N]。
vector<int> dist1 = Dijkstra(1, camp1); // 阵营1最短路
vector<int> dist2 = Dijkstra(2, camp2); // 阵营2最短路
vector<pair<int, int>> vp; // 跨阵营1，2的边 的顶点
vector<int> vplen; // 跨阵营1， 2的边的weight
//再遍历穿越边境的边，比方说<i, j>穿越边境且i、j分别属于阵营1、阵营2，G[i][j]是i到j的距离，
for (int &i : camp1) {
vector<Edge> ve = graph[i];
for (int &j : camp2) {
Edge edge(j, 0);
auto pos = find(ve.begin(), ve.end(), edge);
if (pos != ve.end()) {
vp.push_back(make_pair(i, j));
vplen.push_back(pos->length);
}
}
ve.clear();
}
// 那么G[i][j]+d1[i]+d2[j]就是从这条路过境的总路径长度。找出这类路径长度里最短的那条，输出即可
long long minLen = INT_MAX;
for (int i = 0; i < vp.size(); ++i) {
if (dist1[vp[i].first] == INT_MAX || dist2[vp[i].second] == INT_MAX) {
continue;
}
if (minLen > dist1[vp[i].first] + dist2[vp[i].second] + vplen[i]) {
minLen = dist1[vp[i].first] + dist2[vp[i].second] + vplen[i];
}
}
if (minLen == INT_MAX) cout << -1 << endl;
else cout << minLen << endl;
dist1.clear();
dist2.clear();
camp1.clear();
camp2.clear();
vp.clear();
vplen.clear();
}
return 0;
return 0;
}
发表于 2020-03-12 18:27:30
回复(0)
/*分层图最短路，题目太坑了，说着两城之间最多一条边。数据还有重边，取最小值就行了*/
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define LL long long
using namespace std;
const int AX = 6e2 + 66 ;
int n , m ;
int p[AX];
struct Node {
int u , num ; LL w ;
Node( int u , LL w , int num ):u(u),w(w),num(num) {}
bool operator < ( const Node &a )const {
return w > a.w ;
}
};
LL G[AX][AX] ;
LL dis[2][AX] ;
void djistra() {
memset( dis , 0x3f , sizeof(dis) );
dis[1][1] = 0 ;
priority_queue<Node>q ;
q.push(Node(1,0,1));
while( !q.empty() ) {
Node tmp = q.top();
q.pop() ;
int u = tmp.u ;
int num = tmp.num ;
int t = num ;
for( int i = 2 ; i <= n ; i++ ) {
if( p[i] != p[u] && !num ) continue ;
if( G[u][i] < INF ) {
if( p[i] != p[u] ) t = 0 ;
else t = num ;
if( dis[t][i] > dis[num][u] + G[u][i] ) {
dis[t][i] = dis[num][u] + G[u][i] ;
q.push(Node(i,dis[t][i],t));
}
}
}
}
}
int main() {
int x , y ;
LL w ;
while( ~scanf("%d",&n) && n ) {
memset( G , 0x3f , sizeof(G) ) ;
scanf("%d",&m);
while( m-- ) {
scanf("%d%d%lld",&x,&y,&w);
G[x][y] = min( G[x][y] , w ) ;
G[y][x] = G[x][y] ;
}
for( int i = 1 ; i <= n ; i++ ) {
scanf("%d",&p[i]);
}
djistra();
if( dis[0][2] < INF ) printf("%lld\n",dis[0][2]);
else printf("-1\n");
}
return 0 ;
}
编辑于 2020-03-10 16:16:54
回复(0)
有没有大手子可以解释一下为什么会报这种错误：
段错误:您的程序发生段错误，可能是数组越界，堆栈溢出（比如，递归调用层数太多）等情况引起
#include<iostream>
#define MAX 600
#define INF 10000000
using namespace std;
// N[2, 600] 城市数
// M[0, 10000] 路数
// A B T * M
// leader {1, 2}
int n, G[MAX + 1][MAX + 1];
int d[MAX + 1];
bool vis[MAX + 1] = {false};
int leader[MAX + 1] = {0};
void init(){
int m;
int a, b, t;
for(int i = 0; i < MAX + 1; i++){
for(int j = 0; j < MAX + 1; j++)
G[i][j] = INF;
}
fill(vis, vis + MAX + 1, false);
cin >> m;
for(int i = 1; i <= n; i++){
G[i][i] = 0;
}
for(int i = 0; i < m; i++){
cin >> a >> b >> t;
if(t < G[a][b]){
G[a][b] = t;
G[b][a] = t;
}
}
for(int i = 1; i <= n; i++){
cin >> leader[i];
}
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
if(leader[i] != leader[j]){
G[i][j] = INF;
}
}
}
}
void Dijkstra(int s){
fill(d, d + MAX + 1, INF);
d[s] = 0;
for(int i = 1; i <= n; i++){
int u = 0;
int MIN = INF;
for(int j = 1; j <= n; j++){
if(vis[j] == false && d[j] < MIN){
u = j;
MIN = d[j];
}
}
if(u == 0) return;
vis[u] = true;
for(int v = 1; v <= n; v++){
if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]){
d[v] = d[u] + G[u][v];
}
}
}
}
int main(){
while(true){
int r1, r2;
cin >> n;
if(n == 0) break;
init();
Dijkstra(1);
r1 = d[2];
Dijkstra(2);
r2 = d[1];
if(r1 == INF && r2 == INF){
cout << "-1" << endl;
}
else{
cout << (r1 < r2 ? r1 : r2) << endl;
}
}
return 0;
}
发表于 2019-03-04 21:30:49
回复(1)
// test.cpp: 定义控制台应用程序的入口点。//#include "stdafx.h"#include <cstdio>#include <cstdlib>#include <iostream>#include <vector>#include <limits.h>using namespace std;int camp[605];int dist1[605];int dist2[605];bool mark[605];int n, m;struct edge{int next;int c;};vector<edge>e[605];void dijstra(int dist[], int c) {dist[c] = 0;int newP = c;mark[c] = 1;for (int i = 1; i <n; i++) {//遍历n-1次，把其它节点加进来for (int j = 0; j < e[newP].size(); j++) {//拿newP去更新其它不在K中的点int next= e[newP][j].next;if (camp[next]!=c)continue;if (mark[next] == true)continue;if (dist[next] == -1 || dist[next] > dist[newP] + e[newP][j].c) {dist[next] = dist[newP] + e[newP][j].c;}}int min = 123132131;for (int i = 1; i <= n; i++) {if (mark[i])continue;if (camp[i] != c)continue;if (dist[i] == -1)continue;if (dist[i] < min) {min = dist[i];newP = i;}}mark[newP] = 1;}}int getDis(int m, int n) {for (int i = 0; i < e[m].size();i++) {if (e[m][i].next == n) {//cout <<m<< ":" << n<< e[m][i].c << endl;return e[m][i].c;}}return -1;}int isExist(int x, int y) {for (int i = 0; i < e[x].size(); i++) {if (y == e[x][i].next)return i;}return -1;}int main(){//freopen("in.txt", "r", stdin);while (cin >> n&&n) {cin >> m;for (int i = 1; i <= n; i++) {e[i].clear();dist1[i] = -1;dist2[i] = -1;mark[i] = 0;}for (int i = 0; i < m; i++) {int x, y, cost;cin >> x >> y >> cost;edge tmp;tmp.next = y;tmp.c = cost;int ret = isExist(x, y);if (ret == -1) {e[x].push_back(tmp);tmp.next = x;e[y].push_back(tmp);}else {if (e[x][ret].c > cost){e[x][ret].c = cost;ret = isExist(y, x);e[y][ret].c = cost;}}}for (int i = 1; i <= n; i++) {cin >> camp[i];}dijstra(dist1, 1);dijstra(dist2, 2);int min =INT_MAX;int f = min;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (camp[i] != camp[j]) {if (camp[i] == 1) {if (dist1[i] == -1 || dist2[j] == -1)continue;int d = getDis(i, j);if (d == -1)continue;if (dist1[i] + dist2[j] + d < min) {min = dist1[i] + dist2[j] + d;}}else {if (dist2[i] == -1 || dist1[j] == -1)continue;int d = getDis(i, j);if (d == -1)continue;if (dist2[i] + dist1[j] + d < min) {min = dist2[i] + dist1[j] + d;}}}}}if (min == f)cout << -1 << endl;else cout << min << endl;}return 0;}
发表于 2018-07-03 17:26:42
回复(0)
谁能告诉我，为什么不过了啊，调试了好多次了
package com.speical.improve;
import java.util.Scanner;
/**
* 带约束的最短路径算法
*
* 为什么就是过不了呢？？？？
* @author special
* @date 2017年12月24日 下午3:40:56
*/
public class Pro27Improve3 {
static final int MAX = 100000000;
static int[][] dis;
static int[] cost, support;
static boolean[] flag;
/**
* 最短路径算法
* 带约束的
*
* @param src
* @param drc
*/
public static void dijkral(int src, int drc){
cost[src] = 0;
int length = support.length;
for(int i = 1; i < length; i++){
int start = -1;
int min = MAX;
for(int j = 1; j < length; j++){
if(!flag[j] && cost[j] < min){
start = j;
min = cost[j];
}
}
if(start == drc || start == -1) return;
flag[start] = true;
for(int k = 1; k < length; k++){
if(!flag[k] && min + dis[start][k] < cost[k]
&& support[k] >= support[start]){
cost[k] = min + dis[start][k];
}
}
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
int n = input.nextInt();
if(n == 0) break;
dis = new int[n + 1][n + 1];
support = new int[n + 1];
flag = new boolean[n + 1];
cost = new int[n + 1];
for(int i = 1; i <= n; i++)
cost[i] = MAX;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dis[i][j] = MAX;
int roads = input.nextInt();
int src,drc;
while(roads-- > 0){
src = input.nextInt();
drc = input.nextInt();
dis[src][drc] = input.nextInt();
dis[drc][src] = dis[src][drc];
}
for(int i = 1; i <= n; i++){
support[i] = input.nextInt();
}
dijkral(1,2);
System.out.println(cost[2] == MAX ? -1 : cost[2]);
}
}
}
发表于 2017-12-24 21:22:56
回复(0)
/*跑DJ的时候每个点记录两个值，一个是没有走跨点桥的时候的最短路，一个是走跨点桥的时候的最短路
然后从一个点走到另一个点假如不跨点直接判断能否松弛，否则判断一下当前走跨点桥的机会的用没用，
已经用了的话就不能用了，否则就可以用*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const double esp = 1e-12;
const int ff = 0x3f3f3f3f;
map<int,int>::iterator it;
struct node1
{
int to;
int w;
int ne;
} road[30005];
struct node
{
int pos;
int cost;
int mk;
node(){}
node(int pos = 0,int cost = 0,int mk = 0)
{
this->pos = pos;
this->cost = cost;
this->mk = mk;
}
};
int n,m;
int len;
int head[666];
int dis[2][666];
int num[666];
int vis[2][666];
void add(int f,int to,int w)
{
road[len].to = to;
road[len].w = w;
road[len].ne = head[f];
head[f] = len++;
}
bool operator< (node a,node b)
{
return a.cost> b.cost;
}
void dijkstra()
{
priority_queue<node> q;
q.push(node(1,0,0));
dis[0][1] = dis[1][1] = 0;
while(!q.empty())
{
node t = q.top();
q.pop();
if(vis[t.mk][t.pos]) continue;
for(int i = head[t.pos];i!= -1;i = road[i].ne)
{
int id = road[i].to;
if(num[id]!= num[t.pos])
{
if(t.mk) continue;
if(dis[1][id]> t.cost+road[i].w)
{
dis[1][id] = t.cost+road[i].w;
q.push(node(id,dis[1][id],1));
continue;
}
}
if(t.mk)
{
if(dis[1][id]> t.cost+road[i].w)
{
dis[1][id] = t.cost+road[i].w;
q.push(node(id,dis[1][id],1));
}
}
else
{
if(dis[0][id]> t.cost+road[i].w)
{
dis[0][id] = t.cost+road[i].w;
q.push(node(id,dis[0][id],0));
}
}
}
}
if(dis[0][2] == ff&&dis[1][2] == ff)
printf("-1\n");
else
printf("%d\n",min(dis[0][2],dis[1][2]));
}
void init()
{
mem(dis,ff);
mem(head,-1);
mem(vis,0);
len = 0;
}
int main()
{
while(~scanf("%d",&n))
{
if(n == 0) break;
scanf("%d",&m);
init();
for(int i = 1;i<= m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
for(int i = 1;i<= n;i++)
scanf("%d",&num[i]);
dijkstra();
}
return 0;
}
发表于 2018-05-23 21:26:55
回复(0)
问题信息
难度：
86条回答
134收藏
8526浏览
通过挑战的用户
查看代码-
2023-03-02 10:33:05 -
2023-02-16 19:47:06 -
2023-02-12 22:41:14 -
2023-02-07 19:09:52 -
2023-02-06 23:39:13
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
