中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當前位置: 首頁 > news >正文

亞馬遜網(wǎng)官網(wǎng)首頁四川seo平臺

亞馬遜網(wǎng)官網(wǎng)首頁,四川seo平臺,山西省住房城鄉(xiāng)建設廳網(wǎng)站首頁,東莞網(wǎng)站建設服務公司一、心路歷程 這一個題目寫了三天,可以說是非常掙扎了,明明是例題,但是就是倔強著不去看書上的題解,WA了7次,TLE了4次。 寫了不知道多少條測試用例,一遍一遍的過,一點一點的調(diào)試。 最后終于找到…

一、心路歷程

這一個題目寫了三天,可以說是非常掙扎了,明明是例題,但是就是倔強著不去看書上的題解,WA了7次,TLE了4次。

?寫了不知道多少條測試用例,一遍一遍的過,一點一點的調(diào)試。

?最后終于找到了規(guī)則

二、思路

1、題目要求1到N,必須按照順序排,那么我們就可以認為 對每個 i >1,存在 i -1 到 i?的 0 的斥力

2、我們每一條A到B的排斥力P,看作B到A引力力 P * (-1)

3、規(guī)則1中 斥力,和 輸入的斥力,都按照第二條規(guī)則,轉(zhuǎn)化引力,然后不考慮斥力

4、用 BellmanFord算法,對轉(zhuǎn)換成的和輸入的引力集合,判斷是否存在負圈,存在直接輸出-1

5、不存在負圈,則直接對轉(zhuǎn)換成的和輸入的引力集合使用dijkstra算法,起點是1,如果d[N]大于1000000007(每條邊最大值乘以邊數(shù),加7是為了防止邊界出錯),則輸出-2,否則輸出d[N]。

三、代碼

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node
{int from, to, cost;Node(int from = 0, int to = 0, int cost = 0) : from(from), to(to), cost(cost) {}
};
vector<Node> nodes;
typedef pair<int, int> P;
vector<P> edges[1007];
int d[1007], N, inf = 0x3f3f3f3f, ML, MD, area[1007][1007];
bool used[1007];
void input()
{int from, to, cost;for (int i = 1; i <= ML; i++){scanf("%d%d%d", &from, &to, &cost);edges[from].push_back(P(cost, to));nodes.push_back(Node(from, to, cost));}for (int i = 1; i <= MD; i++){scanf("%d%d%d", &from, &to, &cost);edges[to].push_back(P(-cost, from));nodes.push_back(Node(to, from, -cost));}for (int i = 2; i <= N; i++){edges[i].push_back(P(0, i - 1));nodes.push_back(Node(i, i - 1, -1));}
}
bool bellmanFord(int s)
{bool flag = false;for (int i = 1; i <= N; i++){d[i] = inf;}d[s] = 0;for (int i = 1; i <= N; i++){for (int j = 0; j < nodes.size(); j++){if (d[nodes[j].from] + nodes[j].cost < d[nodes[j].to]){d[nodes[j].to] = d[nodes[j].from] + nodes[j].cost;if (i == N){flag = true;}}}}return flag;
}
void dijkstra(int s)
{for (int i = 1; i <= N; i++){d[i] = inf;used[i] = false;}d[s] = 0;priority_queue<P, vector<P>, greater<P>> que;que.push(P(0, s));while (!que.empty()){P current = que.top();que.pop();if (used[current.second] || current.first > d[current.second]){continue;}for (int i = 0; i < edges[current.second].size(); i++){P toEdge = edges[current.second][i];if (d[current.second] + toEdge.first < d[toEdge.second]){d[toEdge.second] = toEdge.first + d[current.second];que.push(P(d[toEdge.second], toEdge.second));}}}
}
void solve()
{if (bellmanFord(1)){printf("%d\n", -1);}else{dijkstra(1);if (d[N] > 1000000007){printf("%d\n", -2);}else{printf("%d\n", d[N]);}}
}
int main()
{scanf("%d%d%d", &N, &ML, &MD);input();solve();return 0;
}

?

http://www.risenshineclean.com/news/52890.html

相關文章:

  • 做相冊本哪個網(wǎng)站好用嗎短視頻推廣
  • 制作網(wǎng)站公石家莊谷歌seo
  • 做公司網(wǎng)站需要會什么一鍵優(yōu)化表格
  • 有哪些做微博長圖網(wǎng)站澤成seo網(wǎng)站排名
  • 辦文明網(wǎng)站 做文明網(wǎng)民活動關鍵詞查詢網(wǎng)
  • 網(wǎng)絡推廣文案案例鄭州網(wǎng)站seo優(yōu)化公司
  • wordpress黑桃錘擊河北seo網(wǎng)絡推廣
  • 建設銀行網(wǎng)站查詢密碼怎么開通seo的宗旨是什么
  • 廣州新際網(wǎng)站建設公司怎么樣世界球隊最新排名
  • 泰安網(wǎng)站建設公司seo個人優(yōu)化方案案例
  • 網(wǎng)站開發(fā)得花多少錢營業(yè)推廣是一種什么樣的促銷方式
  • 軟件開發(fā)項目實施方案網(wǎng)站seo服務商
  • php做視頻直播網(wǎng)站信息流廣告投放工作內(nèi)容
  • 普通的訂閱號怎么做微網(wǎng)站泉州搜索推廣
  • 工程造價材料信息網(wǎng)山東seo推廣
  • 怎么樣創(chuàng)辦一個網(wǎng)站如何在國外推廣自己的網(wǎng)站
  • 專業(yè)酒店設計網(wǎng)站建設廣州網(wǎng)站快速排名
  • 騙子為啥使用香港服務器seo網(wǎng)站管理
  • dw班級網(wǎng)站建設全國疫情最新情況公布
  • jsp網(wǎng)站開發(fā)實例精講seo外包方案
  • 網(wǎng)站空間 php程序谷歌瀏覽器下載手機版中文
  • 網(wǎng)站制作價格 上海百度網(wǎng)頁推廣怎么做
  • poco攝影網(wǎng)win10優(yōu)化大師官網(wǎng)
  • 撤銷網(wǎng)站備案企業(yè)qq手機版
  • 做時時彩網(wǎng)站平臺有哪些淘寶指數(shù)查詢工具
  • 建筑模板尺寸關鍵詞優(yōu)化營銷
  • 怎么樣建設一個網(wǎng)站關鍵詞排名優(yōu)化報價
  • 從化網(wǎng)站建設適合網(wǎng)絡營銷的產(chǎn)品
  • 佛山免費建站找哪家廣告推廣公司
  • 西安西郊網(wǎng)站建設搜什么關鍵詞你都懂的