原来是要到醋溜站台乘坐醋溜快车到醋溜港”，亮亮解出了地图隐藏的秘密，赶紧奔向醋溜站台，但到了之后，亮亮忧桑地发现，从醋溜站台到醋溜港沿途的每个车站都有很多美女被他飒爽的英姿所吸引，只要经过车站就会被这些漂亮的女孩搭讪，但是现在亮亮一心想要寻找楚楚街而没空去搭理她们，所以亮亮希望在抵达醋溜港的时候被搭讪的次数最少。问亮亮抵达醋溜港最少会被搭讪多少次？
[编程题]旅途
- 热度指数：4282 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行包含两个整数N(2<=N<=5000),M(1<=M<=50000)。N表示公有N个汽车站，M表示公有M条公路，起点为1，终点为N。 第二行包含N个整数(0<=K<=10000)，第i个整数表示在第i站有K个美女想要搭讪亮亮。 接下来M行，每行包含两个整数P(1<=P<=N),Q(1<=Q<=N),代表P,Q两个站是有班车直达的。
输出描述:
一个整数，即亮亮抵达醋溜港最少需要被搭讪的次数。
示例1
输入
5 5 0 1 1 3 6 1 2 1 4 2 3 3 5 4 5
输出
8
//应用dijistra算法解决问题
import java.util.Scanner;
public class Main{
public static void init(int[][] road,int n) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
road[i][j]=Integer.MAX_VALUE;
}
}
}
public static int dijkstra(int[][] road,int s,int n,int girl1) {
int[] dist=new int[n+1];
boolean[] isVisited=new boolean[n+1];
for (int i=2;i<=n;i++) {
dist[i]=road[s][i];
}
dist[s]=girl1;
isVisited[s]=true;
for (int i=2;i<n;i++) {
int minDist=Integer.MAX_VALUE;
int v=1;
for(int j=1;j<=n;j++)
{
if(!isVisited[j]&&dist[j]<minDist)
{
minDist=dist[j];
v=j;
}
}
isVisited[v]=true;
for(int j=1;j<=n;j++)
{
if(!isVisited[j]&&road[v][j]<Integer.MAX_VALUE)
{
int temp=dist[v]+road[v][j];
dist[j]=dist[j]<temp?dist[j]:temp;
}
}
}
return dist[n]+girl1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
while(in.hasNext())
{
int n=in.nextInt();
//表示n个汽车站内有M条公路
int m=in.nextInt();
int[][] road=new int[n+1][n+1];
init(road,n);
int girls[]=new int[n+1];
for(int i=1;i<=n;i++)
{
girls[i]=in.nextInt();
}
for (int i=0;i<m;i++) {
int p=in.nextInt();
int q=in.nextInt();
road[p][q]=girls[q];
road[q][p]=girls[p];
}
System.out.println(dijkstra(road,1,n,girls[1]));
}
}
}
发表于 2016-08-08 19:11:12
回复(3)
//这道千万注意不要认为解中的站台号升序，然后用dp来做
//迪杰斯特拉求解
//
//
#include <iostream>
#include <vector>
#include <set>
#include <string.h>
#include <algorithm>
#include <limits>
using namespace std;
int main()
{
int N,M;
while(cin>>N>>M)
{
vector<vector<int>> graph;
vector<int> cost;
cost.resize(N+1);
graph.resize(N+1);
int i=1,j=N;
while(j--)
cin>>cost[i++];
while(M--)
{
int a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int>dp(N+1,numeric_limits<int>::max());
set<int> visited;
visited.insert(1);
dp[1] = cost[1];
for(int i=0;i<graph[1].size();i++)
dp[graph[1][i]] = dp[1]+cost[graph[1][i]];
while(visited.count(N)==0)
{
int tt = numeric_limits<int>::max();
int temp=-1;
for(int i=1;i<dp.size();i++)
{
if(!visited.count(i))
{
if(dp[i]<tt)
{
tt = dp[i];
temp = i;
}
}
}
visited.insert(temp);
for(int i =0;i<graph[temp].size();i++)
{
dp[graph[temp][i]]=min(dp[temp]+cost[graph[temp][i]],dp[graph[temp][i]]);
}
}
cout<<dp[N]<<endl;
}
return 0;
}
编辑于 2016-08-18 22:11:21
回复(5)
动态规划只能过60%，因为动态规划是一种有向的类似树搜索，但是题目是无向图搜索，意味着可能回转，比如到了5站台回到3站台，所以DIJ算法可以找到全局最优，但是动态规划可能陷入局部最优，它只能看到相邻，一旦局部出现更短的路径，可能在非最优的区域路径上打转。
纪念60%的DP，最短路径算法真的还是有它的道理的......
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
int[][] dp = new int[n+1][n+1];
for(int i=0; i<m; i++){
int a = sc.nextInt();
int b = sc.nextInt();
if(a < b)
dp[a][b] = -1;
else
dp[b][a] = -1;
}
int[] tmp = new int[n+1];
tmp[1] = arr[0];
for(int i=2; i<=n; i++){
tmp[i] = -1;
}
System.out.println(solve(arr, dp, n, tmp));
}
}
public static int solve(int[] arr, int[][] dp, int n, int[] tmp){
for(int i=1; i<=n; i++){
if(tmp[i] != -1){ //i可达，且记录了到i最小的耗散
for(int j=1; j<=n; j++){
if(dp[i][j] == -1){ //ij可达
if(tmp[j] == -1)
tmp[j] = tmp[i] + arr[j-1];
else
tmp[j] = Math.min(tmp[j], tmp[i] + arr[j-1]);
}
}
}
}
return tmp[n];
}
}
发表于 2017-08-22 10:58:10
回复(0)
/**
* 报指针越界？谁能帮我看一下？
*
**/
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int n = scan.nextInt();
int m = scan.nextInt();
int[] girls = new int[n];
for(int i=0;i<n;i++)
girls[i]=scan.nextInt();
int[][] map = new int[n][n];
for(int i=0;i<m;i++){
int p = scan.nextInt();
int q = scan.nextInt();
map[p-1][q-1]=1;
map[q-1][p-1]=1;
}
System.out.println(core(map,0,n,girls));
}
scan.close();
}
private static int core(int[][] map , int row , int n, int[] girls){
if(row==n-1)
return girls[row];
int minMeet = Integer.MAX_VALUE;
for(int i=0;i<n;i++){
if(row!=i&&map[row][i]==1){
int tmp = core(map,i,n,girls);
if(tmp<minMeet)
minMeet = tmp;
}
}
return minMeet+girls[row];
}
}
发表于 2016-08-09 02:37:31
回复(0)
//Dijkstra算法来做
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int M=sc.nextInt();
int[][] weight=new int[N][N];//保存权值的数组
int[] value=new int[N];
for(int i=0;i<N;i++){
value[i]=sc.nextInt();
}
int MAX=2000000;
//初始化weight
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
weight[i][j]=MAX;
}
}
//sc.nextLine();
for(int i=0;i<M;i++){
//String[] s=sc.nextLine().split(" ");
int x=sc.nextInt()-1;
int y=sc.nextInt()-1;
weight[x][y]=value[y];
weight[y][x]=value[x];
}
for(int i=0;i<weight.length;i++){
weight[i][i]=value[i];
}
//weight[0][0]=value[0];
int[] shortPath=dijkstra(weight,0);
int min=shortPath[shortPath.length-1];
System.out.println(min);
}
public static int[] dijkstra1(int[][] weight,int a){
int MAX=10000000;
int n=weight.length;
int[] shortPath = new int[n];
int[] visited = new int[n];
//初始化shortPath
for(int i=0;i<n;i++){
shortPath[i]=MAX;
}
shortPath[0]=weight[0][0];//还没出发前还有权值
visited[0]=1;
//核心
int lastNode=0;//初始化最后一个节点指向开始的节点
for(int count=1;count<n;count++){
int dmin=Integer.MAX_VALUE;
int k=0;//最后节点临时
for(int i=0;i<n;i++){
if(visited[i]==0 && shortPath[lastNode]+weight[lastNode][i]<shortPath[i]){
shortPath[i]=shortPath[lastNode]+weight[lastNode][i];
}
if(visited[i]==0 && shortPath[i]<dmin){
dmin=shortPath[i];
k=i;
}
}
lastNode=k;
visited[k]=1;
}
return shortPath;
}
public static int[] dijkstra(int[][] weight,int start){
int vertexNum = weight.length; //顶点个数
int[] shortPath=new int[vertexNum]; //保存最短路径值
String[] path = new String[vertexNum]; //具体路径存在字符串中
int[] visited = new int[vertexNum]; //顶点i是否已经求过
//初始化
shortPath[start]=weight[start][start];
visited[start]=1;
int M=2000000; //将2000当成无穷大
//初始化shortPath数组
//shortPath[start]=0;
path[start]=start+"";
for(int i=0;i<shortPath.length;i++){
if(i!=start){
shortPath[i]=M;
}
}
int lastNode=start;
for(int count=1;count<vertexNum;count++){
//第一次，weight[0][1],weight[0][2],weight[0][3],..weight[0][5]中取最小的
int dmin = Integer.MAX_VALUE;
int k=0;
for(int i=0;i<vertexNum;i++){
if(visited[i]==0 && shortPath[lastNode]+weight[lastNode][i]<shortPath[i]){
//拿lastNode到i的值+之前shortPath中lastNode的值 和 对应shortPath比较。小则更新路线
//然后再找到一个最小的作为最后的节点
shortPath[i]=shortPath[lastNode]+weight[lastNode][i];
//路线更新存在path数组中
path[i]=path[lastNode]+"-->"+i;
}
if(visited[i]==0 && shortPath[i]<dmin){
dmin=shortPath[i];
k=i;
}
}
lastNode=k;
visited[k]=1;
}
//System.out.println(path[path.length-1]);
return shortPath;
}
}
编辑于 2017-03-31 14:16:49
回复(3)
#include <bits/stdc++.h>
using namespace std;
int dijkstra(vector<vector<int> > &G, vector<int> &w, int n, int s, int e)
{ vector<bool> visited(n+1); vector<int> d(n+1, INT_MAX); d[s] = w[s]; int t = s; int k; while(t != 0) { visited[t] = true; k = 0; for(int i=0;i<G[t].size();i++) { if(!visited[G[t][i]]) d[G[t][i]] = min(d[G[t][i]], d[t]+w[G[t][i]]); } for(int i=1;i<=n;i++) { if(d[i]<d[k] && !visited[i]) k = i; } t = k; } return d[e];
}
int main()
{ int n,m,x,y; while(cin>>n>>m) { vector<vector<int> > G(n+1); vector<int> w(n+1); for(int i=1;i<=n;i++) cin>>w[i]; while(m--) { cin>>x>>y; G[x].push_back(y); G[y].push_back(x); } cout<<dijkstra(G,w,n,1,n)<<endl; } return 0;
}
发表于 2017-12-12 01:07:34
回复(0)
5000的数量级深度优先搜索必然超时
因为这题图不能保证无环所以不能用动态规划
因此只能用Dijkstra算法
算法思想
d[1] = girls[1], d[其他] = 无穷
循环n次{
在所有未标记的节点中 选择d最小的节点x
给x标记
x的所有相邻节点y 更新d[y] = min(d[y], d[x] + girls[y]);
}
最后d[n]即为所求
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;
//无向有环图的最短路径要用dijkstra算法
const int maxn = 5000 + 5;
vector<int> v[maxn];
int girls[maxn], d[maxn], taken[maxn], n, m;
void solve(int N){
while(N--){
int min_d = INT_MAX, x;
for(int i = 1; i <= n; i++)
if(!taken[i] && d[i] < min_d) {x = i;min_d = d[i];}
taken[x] = 1;
for(int i = 0; i < v[x].size(); i++){
d[v[x][i]] = min(d[v[x][i]], d[x] + girls[v[x][i]]);
}
}
}
int main(){
while(scanf("%d%d", &n, &m) == 2){
memset(girls, 0, sizeof(girls));
memset(taken, 0, sizeof(taken));
for(int i = 1; i <= n; i++) scanf("%d", &girls[i]);
for(int i = 0; i < m; i++){
int a, b; scanf("%d%d", &a, &b);
v[a].push_back(b);
v[b].push_back(a);
}
for(int i = 1; i <= n; i++) d[i] = INT_MAX;
d[1] = girls[1];
solve(n);
cout<<d[n]<<endl;
for(int i = 2; i <= n; i++) v[i].clear();
}
return 0;
}
发表于 2018-10-19 18:36:20
回复(1)
#include<bits/stdc++.h>
using namespace std;
struct cmp{
bool operator()(pair<int,int>& a,pair<int,int>& b)
{
return a.first>b.first;
}
};
void dijkstra(int N,vector<vector<int>>& graph,vector<int>& v,vector<int>& d,int s)
{
d[s] = v[s];
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;
pq.push({v[s],s});
while(!pq.empty())
{
auto it = pq.top();pq.pop();
if(it.first>d[it.second]) continue;
int k = it.second;
for(int i=0;i<graph[k].size();++i)
{
int w = d[k]+v[graph[k][i]];
if(w<d[graph[k][i]])
{
d[graph[k][i]] = w;
pq.push({w,graph[k][i]});
}
}
}
}
int main()
{ // 无向有环图上的单源最短路
// dfs超时
// 采用堆优化dijkstra
int N,M;
while(cin>>N>>M)
{
vector<int>v(N+1,0);
for(int i=1;i<=N;++i)
cin>>v[i];
vector<vector<int>>graph(N+1,vector<int>());
vector<int>vis(N+1,0);
for(int i=0;i<M;++i)
{
int a,b;
cin>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int>d(N+1,INT_MAX);
dijkstra(N,graph,v,d,1);
cout<<d[N]<<endl;
}
return 0;
}
发表于 2020-04-18 01:05:40
回复(0)
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
int main(){
int n,m;
while (cin>>n>>m)
{
//保存每站的搭讪次数，从1开始
vector<int> girls(n + 1);
for (int i = 1; i <= n; ++i)
{
cin >> girls[i];
}
//用二维数组保存某一站可以有班车直达的站
vector<vector<int>> graph(n + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i)
{
int x, y;
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
//Dijkstra算法，用一维数组dis来存储1号站到其余各个站的初始搭讪次数
vector<int> dis(n + 1,numeric_limits<int>::max());
dis[1] = girls[1];
for (int i = 0; i < graph[1].size(); ++i)
{
dis[graph[1][i]] = girls[graph[1][i]] + dis[1];
}
//用一维数组book来记录到达该站点是否已经确定有最小的搭讪次数
vector<int> book(n + 1);
for (int i = 2; i <= n; ++i)
{
book[i] = 0;
}
book[1] = 1;
//算法主要部分
for (int i = 0; i < n; ++i)
{
int min = numeric_limits<int>::max();
int flag = 0;//记录最小搭讪次数的站点位置，如果找到，以此为基点坐车去往别的站点，更新别的站点的最小搭讪次数
for (int j = 1; j <= n; ++j)
{
if (book[j]==0 && min > dis[j])
{
min = dis[j];
flag = j;
}
}
if (flag!= 0)
{
book[flag] = 1;
for (int k = 0; k < graph[flag].size(); ++k)
{
if (dis[graph[flag][k]] >(min + girls[graph[flag][k]]))
{
dis[graph[flag][k]] = min + girls[graph[flag][k]];
}
}
}
}
cout << dis[n] <<endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
int main(){
int n,m;
while (cin>>n>>m)
{
//保存每站的搭讪次数，从1开始
vector<int> girls(n + 1);
for (int i = 1; i <= n; ++i)
{
cin >> girls[i];
}
//用二维数组保存某一站可以有班车直达的站
vector<vector<int>> graph(n + 1, vector<int>(n + 1));
for (int i = 0; i < m; ++i)
{
int x, y;
cin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
//Dijkstra算法，用一维数组dis来存储1号站到其余各个站的初始搭讪次数
vector<int> dis(n + 1,numeric_limits<int>::max());
dis[1] = girls[1];
for (int i = 0; i < graph[1].size(); ++i)
{
dis[graph[1][i]] = girls[graph[1][i]] + dis[1];
}
//用一维数组book来记录到达该站点是否已经确定有最小的搭讪次数
vector<int> book(n + 1);
for (int i = 2; i <= n; ++i)
{
book[i] = 0;
}
book[1] = 1;
//算法主要部分
for (int i = 0; i < n; ++i)
{
int min = numeric_limits<int>::max();
int flag = 0;//记录最小搭讪次数的站点位置，如果找到，以此为基点坐车去往别的站点，更新别的站点的最小搭讪次数
for (int j = 1; j <= n; ++j)
{
if (book[j]==0 && min > dis[j])
{
min = dis[j];
flag = j;
}
}
if (flag!= 0)
{
book[flag] = 1;
for (int k = 0; k < graph[flag].size(); ++k)
{
if (dis[graph[flag][k]] >(min + girls[graph[flag][k]]))
{
dis[graph[flag][k]] = min + girls[graph[flag][k]];
}
}
}
}
cout << dis[n] <<endl;
}
return 0;
}
编辑于 2018-08-28 17:48:20
回复(0)
// 迪杰斯特拉算法 求解加权图的最短路径问题
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <climits>
using namespace std;
int find_lowest_cost_id(const vector<int> & costs, const set<int> & processed) {
int min_cost = INT_MAX;
int min_id = -1;
for (int i = 0; i < costs.size(); ++i) {
if ((costs[i] < min_cost) && (processed.count(i) < 1)) {
min_cost = costs[i];
min_id = i;
}
}
return min_id;
}
int main() {
int n = 0;
int m = 0;
while (cin >> n >> m) {
vector<int> girls(n);
for (int i = 0; i < n; ++i) {
cin >> girls[i];
}
vector<set<int>> graph(n);
int x = 0;
int y = 0;
for (int i = 0; i < m; ++i) {
cin >> x >> y;
graph[x - 1].insert(y - 1);
graph[y - 1].insert(x - 1); // 建立连接
}
set<int> processed;
vector<int> costs(n, INT_MAX);
// 更新起点的邻居
costs[0] = girls[0];
for (auto item : graph[0]) {
costs[item] = costs[0] + girls[item];
}
processed.insert(0);
int id = find_lowest_cost_id(costs, processed);
// 选择开销最小的更新其邻居的开销
while (-1 != id) {
for (auto item : graph[id]) { // 更新邻居的开销
if (costs[id] + girls[item] < costs[item]) {
costs[item] = costs[id] + girls[item];
}
}
processed.insert(id);
id = find_lowest_cost_id(costs, processed);
}
cout << costs.back() << endl;
}
return 0;
}
发表于 2018-08-18 19:15:00
回复(0)
标准的Dijkstra可以通过
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define inf 999999
#define white 0
#define black 1
int way[5000+1][5000+1];
int d[5000+1];
int color[5000+1];
int n;
int zuiduan()
{
int minv;
int i,j,u;
for(i=0;i<=n;i++)
{
d[i]=inf;
color[i]=white;
}
d[0]=d[1]=0;
while(1)
{
minv=inf;
u=-1;
for(i=1;i<=n;i++)
{
if(minv>d[i]&&color[i]!=black)
{
u=i;
minv=d[i];
}
}
if(u==-1)break;
color[u]=black;
for(j=1;j<=n;j++)
{
if(color[j]!=black&&way[u][j]!=inf)
{
d[j]=min(way[u][j]+d[u],d[j]);
}
}
}
return d[n];
}
int main(void)
{
int i,j,a,b,m;
cin>>n>>m;
int girls[5000+1];
for(i=1;i<=n;i++)
{
scanf("%d",&girls[i]);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
way[i][j]=inf;
}
}
while(m--)
{
scanf("%d %d",&a,&b);
way[a][b]=girls[b];
way[b][a]=girls[a];
}
a=zuiduan()+girls[1];
cout<<a<<endl;
return 0;
}
发表于 2018-07-30 10:09:57
回复(0)
Python很极限啊，，第一次1500ms过，，优化下650ms，，emmmmmmm
try:
while 1:
import collections
N,M =[int(x) for x in input().split()]
n_list = [int(x) for x in input().split()]
G = collections.defaultdict(dict)
for i in range(M):
s,e = [int(x) for x in input().split()]
G[s][e] = n_list[e-1]
G[e][s] = n_list[s-1]
ans = [float('inf') for i in range(N+1)]
ans[1] = n_list[0]
book = set()
remain = set([i for i in range(N+1)])
minv = 1
while len(book)<len(G.keys()):
book.add(minv)
remain.remove(minv)
for temp_node in G[minv]:
if temp_node in book:
continue
if ans[minv]+G[minv][temp_node]<ans[temp_node]:
ans[temp_node] = ans[minv]+G[minv][temp_node]
temp_add_node = float('inf')
for i in remain:
if ans[i]<temp_add_node:
minv = i
temp_add_node = ans[i]
print(ans[-1])
except EOFError:
pass
发表于 2018-07-10 10:55:46
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <limits.h>
using namespace std;
int n,m;
int main()
{
while(cin>>n>>m)
{
vector<int>chics (n);
for(int i=0;i<n;i++)
cin>>chics[i];
vector<vector<int>> father(n);
int tp0,tp;
for(int i=0;i<m;i++)
{
cin>>tp0>>tp;
father[tp0-1].push_back(tp-1);
father[tp-1].push_back(tp0-1);
}
vector<int> dist(n,INT_MAX);
dist[0]=chics[0];
set<int> vist;
vist.insert(0);
vector<int>::iterator it=father[0].begin();
while(it!=father[0].end())
{
dist[(*it)]=min(dist[(*it)],dist[0]+chics[(*it)]);
it++;
}
while(vist.size()<n-1)
{
int tpp=INT_MAX;
int sig;
for(int i=0;i<n;i++)
{
if(vist.find(i)!=vist.end())
continue;
if(tpp>dist[i])
{
tpp=dist[i];
sig=i;
}
}
vist.insert(sig);
it=father[sig].begin();
while(it!=father[sig].end())
{
dist[(*it)]=min(dist[*it],dist[sig]+chics[*it]);
it++;
}
}
cout<<dist[n-1]<<endl;
}
}
发表于 2018-05-12 11:24:12
回复(0)
//spfa算法求最短路径问题
#include <bits/stdc++.h>
using namespace std;
#define Inf 1<<30
struct Edge
{
int to,dist;
Edge(int t = 0,int d = 0):to(t),dist(d){}
};
vector<list<Edge>>platforms;
vector<int> ***;
int spfa_solve(int n)
{
queue<int> record;
bool *visited = new bool[n+1];
int *dist = new int[n+1];
for(size_t x = 0;x < n+1;++x){
visited[x] = false;
dist[x] = Inf;
}
record.push(1);
visited[1] = true;
dist[1] = ***[1];
int ans = Inf;
while(!record.empty())
{
int head = record.front();
record.pop();
visited[head] = false;
for(auto it = platforms[head].begin();it != platforms[head].end();++it)
{
if(dist[it->to] > dist[head]+it->dist){
dist[it->to] = dist[head]+it->dist;
if(!visited[it->to]){
visited[it->to] = true;
record.push(it->to);
}
}
}
}
ans = dist[n];
return ans;
}
int main()
{
int N,M;
cin >> N >> M;
platforms.resize(N+1);
***.resize(N+1);
for(size_t x = 1;x <= N;++x)cin >> ***[x];
for(size_t x = 1;x <= M;++x){
int f,t;
cin >> f >> t;
platforms[f].push_back(Edge(t,***[t]));
platforms[t].push_back(Edge(f,***[f]));
}
cout << spfa_solve(N) << endl;
return 0;
}
发表于 2018-03-18 10:25:05
回复(0)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main()
{
int N, M;
while (cin >> N >> M)
{
vector<int> bns;
for (int i = 0; i < N; i++)
{
int beauty_num;
cin >> beauty_num;
bns.push_back(beauty_num);
}
vector<vector<int>>path(N, vector<int>(N, 0));
vector<int>visit(N, 0);
for (int i = 0; i < M; i++)
{
int P, Q;
cin >> P >> Q;
path[P - 1][Q - 1] = bns[P - 1];
path[Q - 1][P - 1] = bns[Q - 1];
}
while (1)
{
int min_i = -1;
int min_v = 0x7ffffff;
bool bv = false;
for (int i = 0; i < path[0].size(); i++)
{
if (visit[i] == 0)
{
if (path[0][i] != 0 && path[0][i] < min_v)
{
min_i = i;
min_v = path[0][i];
visit[i] = 1;
bv = true;
}
}
}
if (bv == false)
break;
//update
for (int i = 0; i < path[min_i].size(); i++)
{
if (path[min_i][i] != 0)
{
if (path[0][i] == 0) //无穷
{
if(path[0][min_i] != 0 && path[min_i][i] != 0)
path[0][i] = path[0][min_i] + path[min_i][i];
}
else
{
if(path[min_i][i] != 0 && path[0][min_i] != 0)
if (path[0][i] > (path[0][min_i] + path[min_i][i]))
{
path[0][i] = path[0][min_i] + path[min_i][i];
}
}
}
}
}
cout << path[0][N - 1]+ bns[N-1] << endl;
}
return 0;
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
using namespace std;
int main()
{
int N, M;
while (cin >> N >> M)
{
vector<int> bns;
for (int i = 0; i < N; i++)
{
int beauty_num;
cin >> beauty_num;
bns.push_back(beauty_num);
}
vector<vector<int>>path(N, vector<int>(N, 0));
vector<int>visit(N, 0);
for (int i = 0; i < M; i++)
{
int P, Q;
cin >> P >> Q;
path[P - 1][Q - 1] = bns[P - 1];
path[Q - 1][P - 1] = bns[Q - 1];
}
while (1)
{
int min_i = -1;
int min_v = 0x7ffffff;
bool bv = false;
for (int i = 0; i < path[0].size(); i++)
{
if (visit[i] == 0)
{
if (path[0][i] != 0 && path[0][i] < min_v)
{
min_i = i;
min_v = path[0][i];
visit[i] = 1;
bv = true;
}
}
}
if (bv == false)
break;
//update
for (int i = 0; i < path[min_i].size(); i++)
{
if (path[min_i][i] != 0)
{
if (path[0][i] == 0) //无穷
{
if(path[0][min_i] != 0 && path[min_i][i] != 0)
path[0][i] = path[0][min_i] + path[min_i][i];
}
else
{
if(path[min_i][i] != 0 && path[0][min_i] != 0)
if (path[0][i] > (path[0][min_i] + path[min_i][i]))
{
path[0][i] = path[0][min_i] + path[min_i][i];
}
}
}
}
}
cout << path[0][N - 1]+ bns[N-1] << endl;
}
return 0;
}
只通过了３０趴，有人看看为什么么
发表于 2018-02-10 12:15:09
回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main() {
int INF_MAX = INT32_MAX;
int N, M;
cin >> N >> M;
vector<int> people(N + 1, 0);
vector<vector<int>> map(N + 1);
for (int i = 1;i < N + 1;i++) {
cin >> people[i];
}
for (int i = 0;i < M;i++) {
int x, y;
cin >> x >> y;
map[x].push_back(y);
map[y].push_back(x);
}
vector<int> dist(N + 1, INF_MAX), visited(N + 1, 0);
dist[1] = people[1];
visited[1] = 1;
for (int i = 1;i < N + 1;i++) {
for (int i = 0;i < map[1].size();i++)
dist[map[1][i]] = dist[1] + people[map[1][i]];
}
for (int i = 2;i < N + 1;i++) {
int min = INF_MAX, pos;
for (int k = 1;k < N + 1;k++) {
if (visited[k] == 0 && dist[k] < min) {
min = dist[k];
pos = k;
}
}
visited[pos] = 1;
if (pos == N)
break;
for (int s = 0;s < map[pos].size();s++) {
int p = map[pos][s];
if ((visited[p] == 0) && ((min + people[p]) < dist[p])) {
dist[p] = min + people[p];
}
}
}
cout << dist[N] << endl;
return 0;
}
发表于 2017-06-13 22:00:33
回复(0)
nclude <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int N, M;
int main() {
while(cin >> N >> M) {
vector<int> girls(N, 0);
for (int i = 0; i < N; i++) {
//cin >> girls[i];
scanf("%d", &girls[i]);
}
map<int, set<int>> path;
for (int i = 0; i < M; i++) {
int a, b; scanf("%d %d", &a, &b); //cin >> a >> b;
path[a-1].insert(b-1);
path[b-1].insert(a-1);
}
vector<int> dp(N, INF);
dp[0] = girls[0];
for (int i = 1; i < N; i++) {
for (int j = 0; j < N; j++) {
if (path[j].find(i) != path[j].end())
dp[i] = min(dp[i], dp[j]+girls[i]);
}
}
cout << dp[N-1] << endl;
}
return 0;
}
动态规划只过了60%，没通过的用例没显示完整，测试不了。
不知道这样的思路有什么漏洞，还请大家看看~
用dijkstra写的，只过了90%，提示算法复杂度过大
void dijkstra4(vector<int> &girls, vector<int> &dist, set<int> &noselect, map<int, set<int>> &map1) {
if (noselect.size() == 0)
return;
int minGirls = INF, loc = 0;
for (auto &item : noselect) {
if (dist[item] < minGirls) {
minGirls = dist[item];
loc = item;
}
}
noselect.erase(loc);
for (auto &pos: noselect) {
for (auto &item : map1[pos]) {
dist[pos] = min(dist[pos], dist[item] + girls[pos]);
}
}
dijkstra4(girls, dist, noselect, map1);
}
int main() {
int n, m;
while (cin >> n >> m) {
vector<int> girls(n, 0);
for (int i = 0; i < n; i++) cin >> girls[i];
map<int, set<int>> map1;
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
map1[a-1].insert(b-1);
map1[b-1].insert(a-1);
}
vector<int> dist(n, INF);
dist[0] = girls[0];
for (int i = 1; i < n; i++) {
if (map1[0].find(i) != map1[0].end())
dist[i] =dist[0] + girls[i];
}
//set<int> select{0};
//dijkstra2(girls, dist, select, map1);
//bitset<5005> bitmap;
//bitmap.set(0, 1);
//dijkstra3(girls, dist, bitmap, map1);
set<int> noselect;
for (int i = 1; i < n; i++)
noselect.insert(i);
dijkstra4(girls, dist, noselect, map1);
cout << dist[n-1] << endl;
}
return 0;
}
优化了上面的尾递归，过了。
而且，能用数组模拟的map就尽量用数组来模拟
下面这两条语句，使用map就是不能通过（90%，提示复杂度过高）。使用vector就过了。。
//map<int, set<int>> map1; vector<set<int>> map1(n);
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
int n, m;
while (cin >> n >> m) {
vector<int> girls(n, 0);
for (int i = 0; i < n; i++) cin >> girls[i];
//map<int, set<int>> map1;
vector<set<int>> map1(n);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
map1[a-1].insert(b-1);
map1[b-1].insert(a-1);
}
vector<int> dist(n, INF);
dist[0] = girls[0];
for (int i = 1; i < n; i++) {
if (map1[0].find(i) != map1[0].end())
dist[i] =dist[0] + girls[i];
}
set<int> noselect;
for (int i = 1; i < n; i++)
noselect.insert(i);
while(noselect.size() > 0) {
int minGirls = INF, loc = 0;
for (auto &item : noselect) {
if (dist[item] < minGirls) {
minGirls = dist[item];
loc = item;
}
}
noselect.erase(loc);
for (auto &pos: noselect) {
for (auto &item : map1[pos]) {
dist[pos] = min(dist[pos], dist[item] + girls[pos]);
}
}
}
cout << dist[n-1] << endl;
}
return 0;
}
但好像最后这一版代码，时过时不过的。。。
把vector<set<int>> 改为vector<vector<int>>,
时间瞬间就降了。。
int main() {
int n, m;
while (cin >> n >> m) {
vector<int> girls(n, 0);
for (int i = 0; i < n; i++) cin >> girls[i];
//map<int, set<int>> map1;
vector<vector<int>> map1(n);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
map1[a-1].push_back(b-1);
map1[b-1].push_back(a-1);
}
vector<int> dist(n, INF);
dist[0] = girls[0];
for (int i = 1; i < n; i++) {
if (find(map1[0].begin(), map1[0].end(), i) != map1[0].end())
dist[i] =dist[0] + girls[i];
}
set<int> noselect;
for (int i = 1; i < n; i++)
noselect.insert(i);
while(noselect.size() > 0) {
int minGirls = INF, loc = 0;
for (auto &item : noselect) {
if (dist[item] < minGirls) {
minGirls = dist[item];
loc = item;
}
}
noselect.erase(loc);
for (auto &pos: noselect) {
for (auto &item : map1[pos]) {
dist[pos] = min(dist[pos], dist[item] + girls[pos]);
}
}
}
cout << dist[n-1] << endl;
}
return 0;
}
编辑于 2017-04-11 17:15:56
回复(0)
#Python
#我擦，不容易啊，python卡时间过得950ms，也是醉了
#思路：单源最短路径
# -*- coding:utf-8 -*-
import sys
if __name__ == '__main__':
while True:
nm = sys.stdin.readline().strip()
if not nm:
break
n,m = [int(i) for i in nm.split(' ')]
nums = [int(i) for i in sys.stdin.readline().strip().split(' ')]
mat = {}
for k in range(m):
i,j = [int(i) for i in sys.stdin.readline().strip().split(' ')]
i-=1
j-=1
if i not in mat:
mat[i] = []
mat[i].append(j)
if j not in mat:
mat[j] = []
mat[j].append(i)
res= [float('inf')]*n
vis = [0]*n
res[0] = nums[0]
vis[0] =1
minsInd = None
minsDist = float('inf')
for i in mat[0]:
res[i] = res[0] + nums[i]
if res[i] <minsDist:
minsDist = res[i]
minsInd = i
for i in range(1,n):
vis[minsInd] = 1
for j in mat[minsInd]:
if vis[j]==0 and res[minsInd]+nums[j] < res[j]:
res[j] = res[minsInd] + nums[j]
minsDist = float('inf')
for j in range(n):
if vis[j] ==0 and res[j] <minsDist:
minsDist = res[j]
minsInd = j
print res[-1]
发表于 2017-03-16 21:27:20
回复(0)
为什么会这样？
我理解的是第500个站是要去的地方，我在这里搜500就搜到一个，而且还是前500个数，也就是说这个500是某个站的美女搭讪数
那么这样的话就没有通往500这个站的路了，这应该怎么输出0.0，为什么木有答案
发表于 2017-02-18 11:46:53
回复(1)
#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
#define rep(i,M,N) for (int i = M; i <= N; i++)
#define MIN(x,y) ((x)<(y)?(x):(y))
int Dijkstra(vector<vector<int>> &graph, vector<int> &weight, int n, int start, int end){
vector<bool> visited(n+1);
vector<int> d(n+1, INT_MAX);
d[start] = weight[start];
int temp = start;
int minD;
while(temp!=0){
visited[temp] = true;
minD = 0;
rep(i, 0, graph[temp].size()-1){
if(!visited[graph[temp][i]]) d[graph[temp][i]] = MIN(d[graph[temp][i]], d[temp]+weight[graph[temp][i]]);
}
rep(i, 1, n){
if(d[i]<d[minD]&&!visited[i]) minD = i;
}
temp = minD;
}
return d[end];
}
int main(){
int n,m,x,y;
while(cin>>n>>m){
vector<vector<int>> graph(n+1);
vector<int> weight(n+1);
rep(i, 1, n) cin>>weight[i];
while(m--){
cin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
cout<<Dijkstra(graph, weight, n, 1, n);
}
return 0;
}
编辑于 2016-11-09 13:06:34
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-05 18:51:45 -
2022-08-29 08:48:43 -
2022-08-26 10:41:20
-
2022-08-24 22:46:21
-
2022-07-18 21:50:33
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
