GBX的Graph(最短路)
Problem B: Graph
Time Limit: 2 Sec Memory Limit: cid=1000&pid=1&langmask=16">Submit id=1010">Status
128 MB
Submit: 1 Solved: 1
[
Board]
Description
There are n vertexs and m directed edges. Every vertex has a lowercase letters .Now, ZZT stand at 1.
he want to go to n to find ZZ.But ZZT dont like character strings "cnm" ,"tmd","nsb". so he won't walk such a continuous
3 vertex,the first vertex is 'c' second vertex is 'n' last vertex is 'm'; He wanted to find her as soon as possible.
Input
The first line in the input will contain the number of cases ,Each case begins with two integer n,m(2<=n<=100,m<=1000)
then follow a line contain a character string "a1a2a3a4a5...an" ai is the i vertex's lowercase letter.
then follow m line ,each line contain li,ri,ci , a edge connect li and ri cost time ci(1<=li,r1<=n,1<=ci<=100);
Output
for each case ,output a integer express the minimum time, if can't find ZZ output "-1"(without quotes);
Sample Input
1
4 4
cnmc
1 2 1
2 3 1
1 3 4
3 4 1
Sample Output
5
题意:给你一个n个点m条边的有向图,每个点都有一个小写字母。
如今ZZT站在点1。ZZ站在点n。ZZT想用最短的路程走到ZZ的地方。可是呢,ZZT不希望走过这种连续的三点:cnm,tmd,nsb。如今问你他是否能到达ZZ所在地。
若能,输出最短路径,否则输出-1。
分析:此题关键在于怎样构图。
我们能够把边当点来使用,那么总共同拥有m个点。
增加一个源点0连向以点1发出去的边,增加一个汇点m+1使得点全部指向点n的边连向点m+1,那么原题就变成了从点0開始到达点m+1的最短路径。构图时,当两条边(u,v)。(x,y)中 v == x 而且(str[u],str[v],str[y]) !=(c,n,m),(t,m,d),(n,s,b),则可连接。
构图完成。跑一遍最短路就可以。
题目链接:http://192.168.4.140/problem.php?
cid=1000&pid=1
代码清单:
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<cctype>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull; const int maxn = 100 + 5;
const int maxv = 1000 + 5;
const int max_dis=0x7f7f7f7f; struct Edge{
int to;
int dis;
Edge(){}
Edge(int to,int dis){
this -> to = to;
this -> dis = dis;
}
}; struct E{ int u,v,dis; }edge[maxv]; int T;
int n,m;
int a,b,c;
bool vis[maxv];
int dist[maxv];
char str[maxn];
vector<Edge>graph[maxv]; void init(){
for(int i=0;i<maxv;i++) graph[i].clear();
} void input(){
scanf("%d%d%s",&n,&m,str);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].dis);
}
} bool judge(int pre,int now,int to){
if(str[pre]=='c'&&str[now]=='n'&&str[to]=='m') return true;
if(str[pre]=='t'&&str[now]=='m'&&str[to]=='d') return true;
if(str[pre]=='n'&&str[now]=='s'&&str[to]=='b') return true;
return false;
} void createGraph(){
for(int i=1;i<=m;i++){
if(edge[i].u==1) graph[0].push_back(Edge(i,edge[i].dis));
if(edge[i].v==n) graph[i].push_back(Edge(m+1,0));
for(int j=1;j<=m;j++){
if(i==j) continue;
if(edge[i].v==edge[j].u){
if(judge(edge[i].u-1,edge[i].v-1,edge[j].v-1))
continue;
graph[i].push_back(Edge(j,edge[j].dis));
}
}
}
} int spfa(){
memset(vis,false,sizeof(vis));
memset(dist,max_dis,sizeof(dist));
queue<int>q;
while(!q.empty()) q.pop();
vis[0]=true; dist[0]=0;
q.push(0);
while(!q.empty()){
int u=q.front(); q.pop();
vis[u]=false;
for(int i=0;i<graph[u].size();i++){
int v=graph[u][i].to;
int d=graph[u][i].dis;
if(dist[v]>dist[u]+d){
dist[v]=dist[u]+d;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
if(dist[m+1]==max_dis) return -1;
return dist[m+1];
} void solve(){
createGraph();
printf("%d\n",spfa());
} int main(){
// freopen("cin.txt","r",stdin);
// freopen("cout.txt","w",stdout);
scanf("%d",&T);
while(T--){
init();
input();
solve();
}return 0;
}
最新文章
- Linux C编程学习之C语言简介---预处理、宏、文件包含……
- android 打包失败
- 为什么要做url encode
- friend class
- js ajax 向后台传递数组
- Visual Studio 2012下Box2D开发环境设置
- http://www.ibm.com/developerworks/cn/java/j-lo-hotswapcls/
- 提高你的Java代码质量吧:如果有必要,使用变长数组吧
- MVC 5.0 之奇葩错误-<;类型“ASP._Page__ViewStart_cshtml”不从“System.Web.WebPages.StartPage”继承>;
- Xcoder 7.0 免证书真机测试
- poj2578---三个数中找出第一个大于168的
- linux环境下的线程的创建问题
- 【openstack N版】——走进云计算
- [麻雀虽小]记 简易Markdown阅读器 开发全过程
- First release of mlrMBO - the toolbox for (Bayesian) Black-Box Optimization
- 关于ruby -gem无法切换淘宝源
- Linux后台运行命令 nohup command >; myout.file 2>;&;1
- 《java入门第一季》之面向对象面试题(fianl关键字)
- Servlet 使用ServletContext共享数据,读取web.xml配置
- Go学习笔记(只有链接)