每个输入包含一个测试用例。
输入的第一行包括四个正整数,表示位置个数N(2<=N<=10000),道路条数M(1<=M<=100000),起点位置编号S(1<=S<=N)和快递位置编号T(1<=T<=N)。位置编号从1到N,道路是单向的。数据保证S≠T,保证至少存在一个方案可以从起点位置出发到达快递位置再返回起点位置。
接下来M行,每行包含三个正整数,表示当前道路的起始位置的编号U(1<=U<=N),当前道路通往的位置的编号V(1<=V<=N)和当前道路的距离D(1<=D<=1000)。
对于每个用例,在单独的一行中输出从起点出发抵达快递位置再返回起点的最短距离。
3 3 1 3 1 2 3 2 3 3 3 1 1
7
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static class Item {
int index;
int weight;
public Item(int index, int weight) {
this.index = index;
this.weight = weight;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int len = sc.nextInt();
int times = sc.nextInt();
int start = sc.nextInt();
int end = sc.nextInt();
List<List<Item>> lists = new ArrayList<List<Item>>();
for (int i = 0; i <= len; i++) {
lists.add(new ArrayList<Item>());
}
for (int i = 0; i < times; i++) {
int s = sc.nextInt();
int e = sc.nextInt();
int v = sc.nextInt();
lists.get(s).add(new Item(e, v));
}
int res = helper(lists, len, start, end) + helper(lists, len, end, start);
System.out.println(res);
}
sc.close();
}
public static int helper(List<List<Item>> lists, int len, int start, int end) {
boolean[] visited = new boolean[len + 1];
int[] dis = new int[len + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[start] = 0;
PriorityQueue<Item> queue = new PriorityQueue<Item>(new Comparator<Item>() {
@Override
public int compare(Item o1, Item o2) {
return o1.weight - o2.weight;
}
});
queue.offer(new Item(start, 0));
while (!queue.isEmpty()) {
Item item = queue.poll();
int index = item.index;
if (visited[index]) {
continue;
}
visited[index] = true;
List<Item> list = lists.get(index);
for (int j = 0; j < list.size(); j++) {
Item temp = list.get(j);
if (!visited[temp.index] && dis[index] + temp.weight < dis[temp.index]) {
dis[temp.index] = dis[index] + temp.weight;
queue.offer(new Item(temp.index, dis[index] + temp.weight));
}
}
}
return dis[end];
}
}
#include <stdio.h> #include <stdlib.h> #include <string.h> #define INF 0x3f3f3f3f #define not ! #define and && typedef struct { int to; // 邻接点的编号 int next; // 下一个邻接点的下标 int weight; // 邻接点的权重 } Edge; void addEdge(int* head, Edge* edges, const int u, const int v, const int w, int idx) { (*(edges + idx)).next = *(head + u); (*(edges + idx)).to = v; (*(edges + idx)).weight = w; *(head + u) = idx; } void printAdjList(const int n, int* head, Edge* edges) { int i, u, v, w; for (u = 1; u <= n; ++u) { fprintf(stdout, "vertex %d: [ ", u); for (i = *(head + u); i; i = (*(edges + i)).next) { v = (*(edges + i)).to, w = (*(edges + i)).weight; fprintf(stdout, "(%d, %d) ", v, w); } fputs("]\n", stdout); } fputc(10, stdout); } // 荷兰科学家-迪杰斯特拉算法 int dijkstra_algorithm(int* head, Edge* edges, const int n, int start, int target) { int dists[n + 1]; int visited[n + 1]; memset(dists, INF, sizeof dists); memset(visited, 0x0000, sizeof visited); *(dists + start) = 0; // 源点到源点的距离为0 int i, t, u, v, w, min_dist, selected; for (t = 0; t < n - 1; ++t) { // step 1 min_dist = INF, selected = -1; for (u = 1; u <= n; ++u) { if (not *(visited + u) and *(dists + u) < min_dist) { min_dist = *(dists + u); selected = u; } } // step 2 加入已选顶点集合 if (selected == -1) break; *(visited + selected) = 1; // step 3 进行松驰操作 for (i = *(head + selected); i; i = (*(edges + i)).next) { v = (*(edges + i)).to, w = (*(edges + i)).weight; if (*(visited + v)) continue; if (*(dists + selected) + w < *(dists + v)) *(dists + v) = *(dists + selected) + w; } } return *(dists + target); } int main(const int argc, const char** argv) { int n, m, s, t; fscanf(stdin, "%d %d %d %d", &n, &m, &s, &t); int head[n + 1]; Edge edges[m + 1]; // directed graph memset(head, 0x0000, sizeof head); int i, u, v, w; for (i = 1; i <= m; ++i) { fscanf(stdin, "%d %d %d", &u, &v, &w); addEdge(head, edges, u, v, w, i); } // printAdjList(n, head, edges); int dist = dijkstra_algorithm(head, edges, n, s, t) + dijkstra_algorithm(head, edges, n, t, s); return fprintf(stdout, "%d", dist), 0; }
#include <iostream>
#include <vector>
#include <queue>
#include "assert.h"
using namespace std;
const int N = 10003;
const int INF = 0x3f3f3f3f;
int spfa(int src, int des, vector< pair<int> > mp[], int n)
{
vector<int> dis(n + 1, INF);
vector<bool> used(n + 1, false);
queue<int> que({ src });
dis[src] = 0;
used[src] = true;
while (!que.empty()) {
auto u = que.front();
que.pop();
used[u] = false;
for (auto it = mp[u].begin(); it != mp[u].end(); ++it) {
auto v = it->first, w = it->second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!used[v]) {
used[v] = true;
que.push(v);
}
}
}
}
return dis[des];
}
int main()
{
int n, m, src, des;
cin >> n >> m >> src >> des;
assert(n > 0);
vector< pair<int> > mp[N];
for (int i = 0, u, v, w; i < m; i++) {
cin >> u >> v >> w;
mp[u].emplace_back(v, w);
}
cout << spfa(src, des, mp, n) + spfa(des, src, mp, n) << endl;
system("pause");
return 0;
}
</int></int></bool></int></int></queue></vector></iostream>
Dijkstra's algorithm(迪杰斯特拉算法),但是通过率只有百分之70,求解
//短小精悍的代码~ #include<iostream> #include<queue> #include<cstring> using namespace std; int n,m,s,t; struct Node { int t; int dis; Node(int t,int dis):t(t),dis(dis){} bool operator < (const Node& n)const { return dis>n.dis; } }; vector<Node> V[10002];//vector模拟边表 bool hs[10002];//访问标记 int findPath(int s,int t)//dijkstra优先队列优化 { memset(hs,0,sizeof(hs)); priority_queue<Node> Q; Node tmp(s,0); Q.push(tmp); while(!Q.empty()) { tmp = Q.top(); Q.pop(); int src=tmp.t; int dis=tmp.dis; if(hs[src])//剪枝,弹出的节点已是最短距离,标记不再次进行搜索或放入队列 continue; hs[src]=1; if(src==t) return dis; for(int i=0;i<V[src].size();++i) { int to = V[src][i].t; int todis=dis+V[src][i].dis; if(!hs[to]) { Q.push(Node(to,todis)); } } } return 10000000;//路径不可达 } int main() { cin>>n>>m>>s>>t; int a,b,c; while(m--) { cin>>a>>b>>c; V[a].push_back(Node(b,c)); } int result = findPath(s,t); result+=findPath(t,s); cout<<result<<endl; return 0; }
//贪婪策略,我怎么感觉是牛客网的测试数据出了问题????? let reader=require('readline'); let r1=reader.createInterface({ input:process.stdin,output:process.stdout}); let limit=1000; let table=new Array(); r1.on('line',line=>{ table.push(line.split(" ").map(x=>parseInt(x))) if(table.length==1) limit=table[0][0]; if(table.length==limit+1) { console.log(work(table)); r1.close(); } }); function work(value) { let limit=value[0][1],sum=0; value.shift(); value.sort((x,y)=>{ if(x[1]-x[0]>y[1]-y[0]) return -1; else if((x[1]-x[0]===y[1]-y[0])) return 0; else return 1; }); for(let i=0;i<value.length;i++) { while(value[i][0]<=limit) { sum+=(value[i][1]-value[i][0]); limit-=value[i][0]; } if(limit===0) break; } return sum; }