网店营销推广方案论文/短视频seo询盘系统

这道题有个最多只能转变1次阵营的限制，由题意可知，M出发地是1号，目的地总是2号，从1->2必须转变一次阵营，所以就要求在这之前不能出现2-1的情况，出现了就不符合题目的要求，所以就在Dijkstra中判断松弛条件的时候加一个判断语句就能求解了:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>using namespace std;const int N = 600 + 10;
const int INF = 0x3f3f3f3f;  //对于这个值，我设置成INT_MAX，1e6，1e8都有测试样例通不过，目前只知道0x3f3f3f3f可以通过struct Edge{int to, length;Edge(int t, int l): to(t), length(l){}
};struct Point{int number, distance;Point(int n, int d): number(n), distance(d){}bool operator<(const Point p) const{return distance > p.distance;  //距离小的优先级高}
};vector<Edge> graph[N];
int dis[N], arr[N];void Dijkstra(int s){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 < graph[u].size(); i++){int v = graph[u][i].to;int l = graph[u][i].length;if((dis[u] + l < dis[v]) && !(arr[u] == 2 && arr[v] == 1)){dis[v] = dis[u] + l;pq.push(Point(v, dis[v]));}}}
}int main(){int n, m;while(scanf("%d", &n) != EOF){if(n == 0) break;memset(graph, 0, sizeof(graph));memset(dis, INF, sizeof(dis));scanf("%d", &m);while(m--){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++) scanf("%d", &arr[i]);Dijkstra(1);if(dis[2] != INF) printf("%d\n", dis[2]);else printf("-1\n");}return 0;
}